关于#3及题目的疑问

P1983 [NOIP2013 普及组] 车站分级

Beihai_Jiang @ 2024-10-25 00:30:45

WA#3
输入
10 8
3 1 2 3
3 1 3 5
3 7 8 9
4 1 3 5 6
3 3 5 6
3 1 5 9
5 4 5 6 7 9
3 1 5 10
输出
5
本人的程序和手算的答案
2,8,9为1级
4,6,7为2级
3,5为3级
1为4级
10均可
最后答案为4
请问为什么与数据答案不同

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,rd[N],temp[N],ans;
int cnt,head[N];
bool vis[N][N];
struct Edge{
    int to,next;
}a[N*N];
void AddEdge(int x,int y){
    cnt++;
    a[cnt].to=y;
    a[cnt].next=head[x];
    head[x]=cnt;
}
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch>='0' && ch<='9')
        x=10*x+ch-'0',ch=getchar();
    return x;
}
struct node{
    int id,level;
};
void TopSort(){
    queue<node> q;
    for(int i=1;i<=n;i++)
        if(!rd[i]) q.push((node){i,1});
    while(!q.empty()){
        node f=q.front();
        q.pop();
        ans=max(ans,f.level);
        int u=f.id;
        for(int i=head[u];i;i=a[i].next){
            int v=a[i].to;
            rd[v]--;
            if(!rd[v])
                q.push((node){v,f.level+1});
        }
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int s=read();
        temp[1]=read();
        for(int j=2;j<=s;j++){
            temp[j]=read();
            for(int x=temp[j-1]+1;x<temp[j];x++)
                for(int k=1;k<j;k++){
                    int y=temp[k];
                    if(!vis[x][y]){
                        vis[x][y]=1;
                        AddEdge(x,y);
                        rd[y]++;
                    }
                }
        }
    }
    TopSort();
    cout<<ans;
    return 0;
}

by Beihai_Jiang @ 2024-10-28 22:25:51

本人已ac,此贴结
错误原因:始发站、终点站之间所有级别大于等于火车站x的都必须停靠


|