0分求助
查看原帖
0分求助
763998
switch_on楼主2022/10/23 09:08

自己举的例子都过了,求问到底哪里少考虑了?```

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=5011;
vector<int> G[MAXN];
int du[MAXN],dp[MAXN];

void starting(){
	for(int i=0;i<=MAXN-1;i++){
		dp[i]=1;
	}
} 

int main(){
	starting();
	int m,n,a,b;
	cin>>n>>m;//n是物种数,m是关系数
	for(int i=0;i<m;i++){
		cin>>b>>a;
		G[a].push_back(b);//记录a能吃的物种编号 
		du[b]++;//记录b能被几种动物吃,=0时代表此物种为食物链顶端,作为起点 
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(du[i]==0){
			q.push(i);//记录所有顶端生物编号 
			//cout<<"top= "<<i<<endl;
			dp[i]=1;
		}
	}
	while(!q.empty()){
		int top=q.front();
		//cout<<"top= "<<top<<endl;
		q.pop();
		for(int i=0;i<G[top].size();i++){
			//对于每个能被top吃的物种 
			int to=G[top][i];//记录物种名 
			dp[to]=max(dp[to],dp[top]+1);
			//cout<<"top'dp= "<<dp[top]<<" name= "<<to<<" dp= "<<dp[to]<<endl;
			du[to]--;
			if(du[to]==0){
				//此时to变为顶端 
				//cout<<"now top= "<<to<<endl;
				q.push(to);
			}
		}
	}
	int maxn=0;
	for(int i=1;i<=n;i++){
		maxn=max(maxn,dp[i])%80112002;
	}
	cout<<maxn%80112002<<endl;
	
	return 0;
}

萌新代码,很丑,请dalao帮下忙orz

2022/10/23 09:08
加载中...