2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛 H. Skiing（记忆化dfs）

深碍√TFBOYSˉ_ 2022-06-08 00:45 168阅读 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*≤10000and 0 < M \\leq 1000000<*M*≤100000 as 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

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

题解：

这一题是我a出来的第二个题目，一开始用bfs搜爆了内存，改进了TLE，然后就用dfs尝试了下居然过了。。。不知道别人怎么写的

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define eps 1e-7
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    struct edge
    {
        int to;//该边通往的点
        int len;
    }a[100005];
    int p[10005][105];//存第i个点连接的第j条边是哪个
    int num[10005];//存第i个点连接的边的数目
    int r[10005];//存入度数目
    int vis[10005];//存遍历情况
    int dfs(int tar)//tar为当前点下标
    {
        if(vis[tar])//如果已经遍历过了，直接返回已经保存的最大值
        {
            return vis[tar];
        }
        int i;
        int maxx=0;
        for(i=0;i<num[tar];i++)
        {
            maxx=max(maxx,dfs(a[p[tar][i]].to)+a[p[tar][i]].len);//更新该点之后能遍历的最长长度
        }
        vis[tar]=maxx;//保存
        return maxx;//返回该最大值
    }
    int main()
    {
        int i,j,k,n,m,test,x,y,d;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d%d",&n,&m);
            for(i=1;i<=n;i++)
            {
                num[i]=0;
                r[i]=0;
                vis[i]=0;
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&x,&y,&d);
                a[i].len=d;
                a[i].to=y;
                p[x][num[x]]=i;
                num[x]++;
                r[y]++;
            }
            int maxx=0;
            for(i=1;i<=n;i++)
            {
                if(r[i]==0)//从入度为0的点开始找
                {
                    maxx=max(maxx,dfs(i));//更新最大值
                }
            }
            printf("%d\n",maxx);
        }
        return 0;
    }