关于#3及题目的疑问
查看原帖
关于#3及题目的疑问
359354
Beihai_Jiang楼主2024/10/25 00:30

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;
}
2024/10/25 00:30
加载中...