Skiing 2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛H题(拓扑序求有向图最长路)

参考博客（感谢博主）：http://blog.csdn.net/yo_bc/article/details/77917288

题意：

给定一个有向无环图，求该图的最长路。

思路：

由于是有向无环图，所以最长路肯定是一个入度为0到出度为0的路径，拓扑序在确定当前点之前能够考虑到所有到它的情况，所以最后取个最值即可。

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e4+5;
const int maxm=1e5+5;
struct Node
{
    int v,w,next;
}edge[maxm];
int no,head[maxn];
int t,n,m;
int deg[maxn],val[maxn];
queue<int>q;

void init()
{
    no=0;
    memset(head,-1,sizeof(head));
    memset(deg,0,sizeof(deg));
    memset(val,0,sizeof(val));
}

void topsort()
{
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        if(!deg[i]) q.push(i);
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int k=head[u];k+1;k=edge[k].next){
            int v=edge[k].v;
            val[v]=max(val[v],val[u]+edge[k].w);
            if(--deg[v]==0) q.push(v);
        }
    }
        cout<<*max_element(val+1,val+1+n)<<endl;

}

int main()
{
    for(cin>>t;t--;)
    {
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            edge[no].v=v;edge[no].w=w;
            edge[no].next=head[u],head[u]=no++;
        }
        topsort();
    }
    return 0;
}