蜜汁RE70 数组都双倍开了

Lacer @ 2018-11-03 10:59:13

#include<cstdio>
#include<cstring>
#include<queue>
#define N 2010
using namespace std;
struct VD{int u,dis;};
struct Edge{int to,next;}e[N*N];int tot=0;
int first[N],a[N],in[N];
bool ting[N],book[N][N];
queue<VD>q;
int mmax(int a,int b){return a>b?a:b;}
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        memset(ting,0,sizeof(ting));
        memset(a,0,sizeof(a));
        int si;
        scanf("%d",&si);
        for(i=1;i<=si;i++){scanf("%d",&a[i]);ting[a[i]]=true;}
        for(i=a[1];i<=a[si];i++)
        {
            if(ting[i])continue;
            for(j=1;j<=si;j++)
            {
                if(!book[i][a[j]])
                e[++tot]=(Edge){a[j],first[i]};first[i]=tot;
                in[a[j]]++;
            }
        }
    }
    int ans=0;memset(a,0,sizeof(a));
    for(i=1;i<=n;i++)if(!in[i]){q.push((VD){i,1});a[i]=1;}
    while(!q.empty())
    {
        int u=q.front().u;ans=mmax(q.front().dis,ans);
        int k=first[u];
        while(k){
            int v=e[k].to;k=e[k].next;
            if(a[v])continue;
            if(--in[v]==0){q.push((VD){v,q.front().dis+1});a[v]=1;}
        }
        q.pop();
    }
    printf("%d",ans);
    return 0;
}

by MZMH @ 2018-11-03 11:04:48

去 蒟蒻(大佬)问答所 看看

by Dark_Van @ 2019-02-05 18:54:03

同RE60分，楼主解开了吗？

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 20100;

int n,m,rud[MAX]={0};
int first[MAX];
int ans=0;

int read(){
    int x=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*w;
}

struct edge{
    int u,v,next;
}e[MAX];

struct node{
    int u,len;
};

int cnt=0;
void insert(int u,int v){
    ++cnt;e[cnt].u=u;e[cnt].v=v;e[cnt].next=first[u];first[u]=cnt;
}

node makenode(int u,int len){
    node qwq;
    qwq.len=len;qwq.u=u;
    return qwq;
}

queue<node> q;
void topo(){
    for(int i=1;i<=n;i++){
        if(rud[i]==0)q.push(makenode(i,1));
    }
    ans=1;
    while(!q.empty()){
        int u=q.front().u,len=q.front().len;
        q.pop();
        for(int i=first[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            rud[v]--;
            if(rud[v]==0){
                q.push(makenode(v,len+1));
                ans=max(ans,len+1);
            } 
        }
    }
} 

int con[MAX][MAX]={0};
int main(){
    memset(first,-1,sizeof(first));
    n=read();m=read();
    int temp[MAX],stop[MAX];
    for(int i=1;i<=m;i++){
        memset(stop,0,sizeof(stop));
        int tot=read();
        for(int j=1;j<=tot;j++){
            temp[j]=read();
            stop[temp[j]]=1;
        }
        for(int j=temp[1];j<=temp[tot];j++){
            if(!stop[j]){
                for(int k=1;k<=tot;k++){
                    if(!con[j][temp[k]]){
                        con[j][temp[k]]=1;
                        insert(j,temp[k]);
                        rud[temp[k]]++;
                    }
                }
            }
        }
    }
    topo();
    printf("%d",ans);
    return 0;
}