40分求助

P1983 [NOIP2013 普及组] 车站分级

CAICAIA @ 2023-08-13 19:02:07

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int to;
    int last;
}edge[1001000];
int head[1100]={0},in[1100]={0},k=0;;
void add(int x,int y){
    k++;
    edge[k].to=y;
    edge[k].last=head[x];
    head[x]=k;
}
int aa[1100]={0};
int main(){
    int x;
    int sum=0,ans=0;
    scanf("%d %d",&n,&m);
    bool flag[1100]={0};
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        for(int j=1;j<=x;j++){
            scanf("%d",&aa[j]);
        }
        int ki=2;
        for(int j=aa[1]+1;j<aa[x];j++){
            if(j==aa[ki]){
                ki++;
                continue;
            }
            for(int o=1;o<=x;o++){
                add(j,aa[o]);
                in[aa[o]]++;
                sum++;
            }
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=head[i];j!=0;j=edge[j].last){
            printf("%d to %d\n",i,edge[j].to);

        }
        //printf("i=%d %d\n",i,in[i]);
    }
    */

    while(sum>0){
        for(int i=1;i<=n;i++){
            if(in[i]==0&&flag[i]==0){
                for(int j=head[i];j!=0;j=edge[j].last){
                    in[edge[j].to]--;
                    //printf("%d to %d\n",i,edge[j].to);
                    sum--;
                }
                flag[i]=1;
            }
        }
        ans++;
        /*
        for(int i=1;i<=n;i++){
            printf("%d ",in[i]);
        }
        printf("\nsum=%d\n",sum);
        */
    }
    /*
    for(int i=1;i<=n;i++){
        printf("%d ",in[i]);
    }
    */
    cout<<ans+1;
    return 0;
}

by CAICAIA @ 2023-08-13 19:02:45

样例全过

3re 3wa


by shaboyi @ 2023-08-23 15:36:31

@Dai_Fu 优化下


|