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的都必须停靠