一道拓扑排序+动态规划的题目
  • 板块学术版
  • 楼主魏老师
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/28 17:15
  • 上次更新2024/8/28 19:50:48
查看原帖
一道拓扑排序+动态规划的题目
285961
魏老师楼主2024/8/28 17:15

样例都过,但是提交只对俩!,不知道为什么?

#include<bits/stdc++.h>
using namespace std;
int a[10010][10010],ans[10010],f[10010];
int q[10010],r[10010],n,m,num=0;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>y>>x;
		a[x][y]=1;
		r[y]++;
	}
	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--];
		q[++num]=temp;
		for(int i=1;i<=n;i++)
		{
			if(a[temp][i]!=0)
			{
				r[i]--;
				if(r[i]==0) ans[++top]=i;
			}
		}
	}
	if(num!=n)
	{
		cout<<"Poor Xed"<<endl;
		return 0;
	}
	int k=2;
	while(k<=n)
	{
		for(int i=1;i<=k-1;i++)
		{
			if(a[q[i]][q[k]]!=0)
			{
				if(f[q[k]]<f[q[i]]+1) f[q[k]]=f[q[i]]+1;
			}
		}
		k++;
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=f[i];
	}
	cout<<sum<<endl;
	return 0;
}
2024/8/28 17:15
加载中...