摘要：
想法：因为它是一个有向无环图，所以最长的路径必须是入口度为0到出口度为0的路径。拓扑顺序可以在确定当前点之前考虑其所有条件，因此可以取最后一个值。
参考博客（感谢博主）：http://blog.csdn.net/yo_bc/article/details/77917288
题意：
给定一个有向无环图，求该图的最长路。
思路：
由于是有向无环图，所以最长路肯定是一个入度为0到出度为0的路径，拓扑序在确定当前点之前能够考虑到所有到它的情况，所以最后取个最值即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxn=1e4+5; 5 const int maxm=1e5+5; 6 struct Node 7 { 8 int v,w,next; 9 }edge[maxm]; 10 int no,head[maxn]; 11 int t,n,m; 12 int deg[maxn],val[maxn]; 13 queue<int>q; 14 15 void init() 16 { 17 no=0; 18 memset(head,-1,sizeof(head)); 19 memset(deg,0,sizeof(deg)); 20 memset(val,0,sizeof(val)); 21 } 22 23 void topsort() 24 { 25 while(!q.empty()) q.pop(); 26 for(int i=1;i<=n;i++) 27 if(!deg[i]) q.push(i); 28 int ans=0; 29 while(!q.empty()) 30 { 31 int u=q.front();q.pop(); 32 for(int k=head[u];k+1;k=edge[k].next){ 33 int v=edge[k].v; 34 val[v]=max(val[v],val[u]+edge[k].w); 35 if(--deg[v]==0) q.push(v); 36 } 37 } 38 cout<<*max_element(val+1,val+1+n)<<endl; 39 40 } 41 42 int main() 43 { 44 for(cin>>t;t--;) 45 { 46 cin>>n>>m; 47 init(); 48 for(int i=1;i<=m;i++){ 49 int u,v,w; 50 cin>>u>>v>>w; 51 edge[no].v=v;edge[no].w=w; 52 edge[no].next=head[u],head[u]=no++; 53 } 54 topsort(); 55 } 56 return 0; 57 }