题目链接：3249 -- Test for Job
样例输入：
6 5
1
2
2
3
3
4
1 2
1 3
2 4
3 4
5 6样例输出:
7简化题意：给定一个图，让求从入度为0的点到出度为0的点的一条路径，使得路径上的节点值之和最大。
这道题给定的图是由多个拓扑图组成的。所以出度为0的点不止一个，每次遇到出度为0的点都要更新当前的最大值，不知道拓扑图如何遍历的小伙伴可以看下这里：拓扑排序详解_AC__dream的博客-CSDN博客_拓扑序列怎么求
设f[i]表示到节点i的所有路径中节点值之和最大的值，但是需要注意的一点就是由于节点值可能为负值，所以我们一开始要把所有的f数组设置为负无穷大。其他就没什么了，细节见代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+10;
long long w[N],f[N],in[N],n,m;
vector<int>p[N];
long long Top_sort()
{
long long ans=-1e12;//结果可能为负数
queue<int>q;
for(int i=1;i<=n;i++)
{
if(!in[i])
{
f[i]=w[i];
q.push(i);
}
}
while(!q.empty())
{
int t=q.front();
if(p[t].size()==0)//(此处不能直接返回，因为可能有多个终点)
ans=max(ans,f[t]);
q.pop();
for(int i=0;i<p[t].size();i++)
{
int tt=p[t][i];
f[tt]=max(f[tt],w[tt]+f[t]);
in[tt]--;
if(!in[tt]) q.push(tt);
}
}
return ans;
}
int main()
{
int u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]),p[i].clear(),f[i]=-1e12,in[i]=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
p[u].push_back(v);
in[v]++;
}
printf("%lld\n",Top_sort());
}
return 0;
} 
