图论的一道题目,只得20分,请大神指教
  • 板块学术版
  • 楼主魏老师
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/8/30 19:02
  • 上次更新2024/8/30 21:55:02
查看原帖
图论的一道题目,只得20分,请大神指教
285961
魏老师楼主2024/8/30 19:02

#include<bits/stdc++.h>
using namespace std;
int a[10010][301],b[10010][301],ans[10010],f[10010];
int r[10010],n,m,num=0;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[y][0]++;
		a[y][a[y][0]]=x;
		r[x]++;//统计入度 
	}
	int temp,top=-1;
	for(int i=1;i<=n;i++)
	{
		f[i]=100; 
		if(r[i]==0)
		{
			ans[++top]=i;
		}
	}
	while(top!=-1)
	{
		int temp=ans[top--];
		++num;
		for(int i=1;i<=a[temp][0];i++)
		{
			r[a[temp][i]]--;
			if(r[a[temp][i]]==0)
			{
				ans[++top]=a[temp][i];
				f[ans[top]]=f[temp]+1;
			}
		}
	}
	if(num!=n)
	{
		cout<<"Poor Xed"<<endl;
		return 0;
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=f[i];
	}
	cout<<sum<<endl;
	return 0;
}
/*
6 9
2 1
3 1
6 1
3 2
4 2
5 2
6 3
6 4
6 5
*/
2024/8/30 19:02
加载中...