Shortest Path(树形DP)

Shortest Path

https://ac.nowcoder.com/acm/problem/13886


题目:

一棵偶数结点的树,边带权。请将结点分成n/2对点,使每对点路径求和最小。


做法:










代码:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << 
using namespace std;
typedef long long ll;
const int N = 1e4 + 7;
vector<pair<int,int> > g[N];
int mrk[N];
ll dp[N];
void dfs(int u, int p){
    int cnt = 0;//记录u子树中未配对儿子数
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (v == p) continue;
        dfs(v, u);//先处理子树v
        dp[u] += dp[v];//v子树的解累加进u子树
        if (!mrk[v]) dp[u] += w, cnt++;//如果结点v在v子树里没下场配对,则v必定在u子树配对,边权加上,cnt++
    }
    if (cnt%2){//未配对儿子奇数,u下场配对
        mrk[u] = 1;//记录u已配对
    }else{
        mrk[u] = 0;//未配对儿子偶数,它们两两配对,u不下场
    }
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) g[i].clear();
        memset(mrk, 0, sizeof mrk);
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < n-1; ++i){
            int u, v, w; cin >> u >> v >> w;
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        dfs(1, 1);
        cout << dp[1] << endl;
    }
    return 0;
}
全部评论

相关推荐

od现在都成这样了&nbsp;就业市场真是crazy
牛客473059135号:没事,我有个朋友是985本硕学计算机的,被华为卡目标院校了简历挂,不过不是od虽然人家拿到一堆别的offer了就挺搞笑的属于是……
点赞 评论 收藏
分享
04-30 21:35
已编辑
长安大学 C++
晓沐咕咕咕:评论区没被女朋友好好对待过的计小将可真多。觉得可惜可以理解,毕竟一线大厂sp。但是骂楼主糊涂的大可不必,说什么会被社会毒打更是丢人。女朋友体制内生活有保障,读研女朋友还供着,都准备订婚了人家两情相悦,二线本地以后两口子日子美滋滋,哪轮到你一个一线城市房子都买不起的996清高计小将在这说人家傻😅
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务