求助,本地和测试输出不同,在线IDE输出同本地

P1983 [NOIP2013 普及组] 车站分级

Mr_think @ 2021-02-02 08:52:52

虚点做法

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;
int n,m,ans=0;
bool vis[N*N];
int du[N],f[N*N];
int hd[N*N],nt[N*N],e[N*N],cnt=0;
inline int maxx(int x,int y){return x>=y?x:y;}
inline void tian(int x,int y){
    e[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
    du[y]++;
}
inline void topo(){
    queue<int> q;
    int p=m+n;
    for(int i=1;i<=p;i++){
        if(!du[i]){
            q.push(i);
            if(i<=n) f[i]=1;
            else     f[i]=0;
        }
    }
    while(q.size()){
        int x=q.front();   q.pop();
        for(int i=hd[x];i;i=nt[i]){
            int y=e[i];
            if(y<=n) f[y]=maxx(f[x]+1,f[y]);
            else     f[y]=maxx(f[x],f[y]);
            ans=maxx(ans,f[y]);
            if(--du[y]==0)
                q.push(y);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        memset(vis,0,sizeof(vis));
        int s;scanf("%d",&s);
        int tou,wei,xu=n+i;
        for(int j=1;j<=s;j++){
            int a;scanf("%d",&a);
            if(j==1) tou=a;
            if(j==s) wei=a;
            vis[a]=1;
            tian(xu,a);
        }
        for(int j=tou;j<=wei;j++)
            if(!vis[j]) tian(j,xu);
    }
    topo();
    printf("%d",ans);
    return 0;
}

by iMya_nlgau @ 2021-02-02 09:34:11

@Mr_think 把你的 N 开到 2005 就过了 https://www.luogu.com.cn/record/45964774

大概是数组开小了 (


by Mr_think @ 2021-02-02 09:56:55

感谢


|