垃圾学渣求毕业 2021-12-18 21:39 采纳率: 50%
浏览 140
已结题

C++ 树形dp练习题 最长路径

问题描述:
有一个新开的水上乐园,业主准备用它最大的景点“滑梯的天堂”作为宣传来吸引顾客。
这是一个巨大的水滑梯网络,覆盖整个山腰。每个滑道的的末端都有一个平台,通常与至少一个其他滑道的起点相连,可以进一步下滑(有些不是,那些所谓的侧出口为客人提供了提前离开景点的可能性)。客人从顶部平台开始,通过众多滑道序列中的一个,一路下滑到底层平台(或其中一个侧出口)
由于他们认为顾客一般从顶层平台滑到底层平台的可能性最大,所以业主想在广告中使用这个数字,你可以帮他们计算一下吗?

输入:

  • 一行包括N,M,s和t (2 ≤ N ≤ 5 · 10^4, 0 ≤ M ≤ 2 · 10^5,1 ≤ s, t ≤ N) 分别代表平台的数量,滑道的数量,顶部平台和底层平台的指数
  • M行用来描述滑道,第i行包括整数$b_i$和$e_i$ (1 ≤ $b_i$, $e_i$ ≤ N, bi≠ei) 表示一个滑道从平台$b_i$开始,到平台$e_i$结束。

It is guaranteed that no slides end in the top platform s or start in the bottom platform t and that one can’t get to a platform one has already slid down from without leaving the attraction in the meantime.

输出:
输出上面指定的可能性的数量,结果不超过10^16.

inputoutput
4 5 1 43
1 2-
2 3-
1 4-
2 4-
3 4-
------------
7 8 1 74
1 2-
1 3-
2 4-
3 4-
4 5-
4 6-
5 7-
6 7-
------------
5 7 1 55
1 2-
1 3-
1 4-
2 3-
3 4-
3 5-
4 5-
  • 写回答

5条回答 默认 最新

  • Clarence Liu 2021-12-23 10:52
    关注
    
    #include <iostream>
    #include <vector>
    #include <functional>
    #include <queue>
    
    using namespace std;
    
    typedef long long ll;
    int main(){
        int n, m, s, t;
        cin >> n >> m >> s >> t;
        vector<vector<int> > g(n + 1);
        vector<ll> dp(n + 1);
        for(int i=0;i<m;i++){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
        }
        vector<bool> used(n + 1);
        function<ll(int)> Dfs = [&](int u){
            if(used[u]){
                return dp[u];
            }
            used[u] = true;
            for(int i=0;i<g[u].size();i++){
                int v = g[u][i];
                dp[u] += Dfs(v);
            }
            return dp[u];
        };
        used[t] = true;
        dp[t] = 1;
        cout << Dfs(s);
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

问题事件

  • 系统已结题 12月31日
  • 已采纳回答 12月23日
  • 赞助了问题酬金 12月19日
  • 创建了问题 12月18日