思路：我们首先来一遍拓扑排序，将点按先后顺序排列于一维数组中，然后扫描一遍数组，将每个点的出边所连接的点进行更新，即可得到最优解。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define inf 2000000010 #define Maxn 100010 #define Maxm 1000010 using namespace std; int dist[Maxn],vi[Maxn],index[Maxn],e,value[Maxn],indegree[Maxn],outdegree[Maxn],ans[Maxn],num,n; struct Edge{ int to,next,val; }edge[Maxm]; void addedge(int from ,int to ,int val ) { edge[e].to=to; edge[e].val=val; edge[e].next=index[from]; index[from]=e++; } int Max=-inf; void Topsort() { queue<int> q; int i,j,k,now,adj; for(i=1;i<=n;i++) { if(indegree[i]==0) { q.push(i); dist[i]=value[i]; } } while(!q.empty()) { now=q.front(); ans[num++]=now; q.pop(); for(i=index[now];i!=-1;i=edge[i].next) { adj=edge[i].to; indegree[adj]--; if(!indegree[adj]) q.push(adj); } } for(i=1;i<num;i++) { //cout<<ans[i]<<" "; for(j=index[ans[i]];j!=-1;j=edge[j].next) { dist[edge[j].to]=max(dist[edge[j].to],dist[ans[i]]+edge[j].val); } if(outdegree[ans[i]]==0) { if(dist[ans[i]]>Max) Max=dist[ans[i]]; } } //cout<<endl; } void init() { memset(indegree,0,sizeof(indegree)); memset(outdegree,0,sizeof(outdegree)); memset(index,-1,sizeof(index)); memset(vi,0,sizeof(vi)); memset(ans,0,sizeof(ans)); for(int i=0;i<=100010;i++) dist[i]=-inf; Max=-inf; e=0; num=1; } int main() { int m,i,j,a,b,val; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=n;i++) scanf("%d",&value[i]); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b,value[b]); indegree[b]++,outdegree[a]++; } Topsort(); //for(i=1;i<=n;i++) //cout<<dist[i]<<endl; printf("%d ",Max); } return 0; }