拓扑排序

悠悠 2022-06-08 06:19 49阅读 0赞

In this winter holiday, Bob has a plan for skiing at the mountain resort.

This ski resort has M*M* different ski paths and N*N* different flags situated at those turning points.

The i*i*\-th path from the S\_i*S**i*\-th flag to the T\_i*T**i*\-th flag has length L\_i*L**i*.

Each path must follow the principal of reduction of heights and the start point must be higher than the end point strictly.

An available ski trail would start from a flag, passing through several flags along the paths, and end at another flag.

Now, you should help Bob find the longest available ski trail in the ski resort.

### Input Format ###

The first line contains an integer T*T*, indicating that there are T*T* cases.

In each test case, the first line contains two integers N*N* and M*M* where 0 < N \\leq 100000<*N*≤10000 and 0 < M \\leq 1000000<*M*≤100000as described above.

Each of the following M*M* lines contains three integers S\_i*S**i*, T\_i*T**i*, and L\_i~(0 < L\_i < 1000)*L**i* (0<*L**i*<1000) describing a path in the ski resort.

### Output Format ###

For each test case, ouput one integer representing the length of the longest ski trail.

#### 样例输入 ####

1
    5 4
    1 3 3
    2 3 4
    3 4 1
    3 5 2

#### 样例输出 ####

#### 题目来源 ####

[2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛][2017 ACM-ICPC]

最长路径：

\#include <iostream>  
\#include <cstdio>  
\#include <cstring>  
\#include <algorithm>  
\#include <queue>  
\#include <vector>  
\#define inf 0x3f3f3f  
\#define ms(x) memset(x,0,sizeof(x))  
\#define mf(x) memset(x,-1,sizeof(x))  
using namespace std;  
const int N = 20002;  
struct node  
\{  
    int y,z;  
    node() \{\}  
    node(int ty, int tz): y(ty), z(tz) \{\}  
\};  
vector<node>q\[N\];  
int in\[N\];  
int f\[N\];  
int main()  
\{  
    int T;  
    int n,m;  
    scanf("%d",&T);  
    while(T--)  
    \{  
        queue<int>que;  
        ms(in);  
        ms(f);  
        int ans = 0;  
        scanf("%d%d",&n,&m);  
        for(int i=1; i<=n; i++)  
            q\[i\].clear();  
        for(int i=0; i<m; i++)  
        \{  
            int x, y, z;  
            scanf("%d%d%d",&x,&y,&z);  
            q\[x\].push\_back(node(y,z));  
            in\[y\]++;  
        \}  
        for(int i=1; i<=n; i++)  
        \{  
            if(!in\[i\])  
            que.push(i);  
        \}  
        while(!que.empty())  
        \{  
            int cur = que.front();  
            que.pop();  
            for(int i=0; i<q\[cur\].size(); i++)  
            \{  
                int v = q\[cur\]\[i\].y;  
                int w = q\[cur\]\[i\].z;  
                f\[v\] = max(f\[v\],f\[cur\]+w);  
                ans = max(ans, f\[v\]);  
                in\[v\]--;  
                if(!in\[v\])  
                que.push(v);  
            \}  
        \}  
        cout<<ans<<endl;  
    \}  
    return 0;  
\}

[2017 ACM-ICPC]: https://nanti.jisuanke.com/?kw=2017%20ACM-ICPC%20%E4%BA%9A%E6%B4%B2%E5%8C%BA%EF%BC%88%E4%B9%8C%E9%B2%81%E6%9C%A8%E9%BD%90%E8%B5%9B%E5%8C%BA%EF%BC%89%E7%BD%91%E7%BB%9C%E8%B5%9B