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.

#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;
}

#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<int> in(n + 1);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v] += 1;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i] == 0) q.push(i);
    }
    vector<ll> ans(n + 1);
    ans[s] = 1ll;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i];
            in[v] -= 1;
            ans[v] += ans[u];
            if(in[v] == 0){
                q.push(v);
            }
        }
    }
    cout << ans[t];
    return 0;
}

是要求最长路径还是要求可能的路径数量

可以采用模拟退火这类启发式算法试试

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<int> > g(n + 1);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    vector<ll> dp(n + 1);
    dp[s] = 1;
    queue<int> q;
    q.push(s);
    vector<bool> vis(n + 1);
    while(!q.empty()){
        auto u = q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto v : g[u]){
            dp[v] += dp[u];
            q.push(v);
        }
    }
    cout << dp[t];
    return 0;
}