题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4313
题意：
给定$n$个点的一棵树及树边权值，要求去掉一些边使得给定的$m$个坏点不再连通，求最小花费。
数据范围：$2 \le n \le 100,000, 2 \le m \le n$
分析：
最小生成树
将每个坏点看成一个连通块，我们希望将权值大的边保留下来，按照树边从大到小排序，重新建树，若加上某一条边后连通块相连，就要删去该边。
树形dp
设$dp[i][0]$表示对于结点$i$，其与子树组成的连通块中仅有一个坏点的最小花费。由于求的是最小值，所以我们用$inf$来表示不可到达的状态。
那么若该点为坏点，则dp[i][0] = inf, dp[i][1] += min(dp[v][0], dp[v][1] + cost);
若非坏点，则dp[i][0] += min(dp[v][0], dp[v][1] + cost); dp[i][1] = min{dp[i][0] - min(dp[v][0], dp[v][1] + cost) +dp[i][1]}
代码：
最小生成树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| > File Name: 4313.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/10/12 9:30:15 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; const int maxn = 1e5 + 5; typedef long long ll; struct EDGE{ int from, to, cost; bool operator < (const EDGE& a)const{ if(cost == a.cost && from == a.from) return to < a.to; else if(cost == a.cost) return from < a.from; return cost < a.cost; } }edge[maxn + 1]; int pa[maxn]; int _find(int x) { if(x == pa[x]) return x; return pa[x] = _find(pa[x]); } void unit(int u, int v) { int ru = _find(u), rv = _find(v); if(ru == rv) return; pa[ru] = rv; } bool vis[maxn]; int main (void) { int T;scanf("%d", &T); while(T--){ int tot = 0; int n, k;scanf("%d%d", &n, &k); int u, v, x; for(int i = 0; i < n; ++i) pa[i] = i; for(int i = 0; i < n - 1; ++i){ scanf("%d%d%d", &u, &v, &x); edge[tot++] = (EDGE){u, v, x}; } memset(vis, false, sizeof(vis)); for(int i = 0; i < k; ++i){ scanf("%d", &v); vis[v] = true; } ll ans = 0; sort(edge, edge + tot); for(int i = tot - 1; i >= 0; --i){ u = edge[i].from, v = edge[i].to; int ru = _find(u), rv = _find(v); if(vis[ru] && vis[rv]) ans += edge[i].cost; else if(vis[ru]) unit(v, u); else unit(u, v); } printf("%lld\n", ans); } return 0; }
|
树形dp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
| > File Name: 4313.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/10/12 9:30:15 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; const int maxn = 1e5 + 5; typedef long long ll; ll oo = 1234567891011; struct EDGE{ int next, to, cost; }edge[maxn * 2 + 1]; ll dp[maxn][2]; bool vis[maxn]; int root; int tot; int head[maxn]; void addedge(int u, int v, int cost) { edge[tot].next = head[u]; edge[tot].to = v; edge[tot].cost = cost; head[u] = tot++; } void dfs(int now, int pa) { if(vis[now]) dp[now][1] = 0, dp[now][0] = oo; else dp[now][0] = 0, dp[now][1] = oo; for(int i = head[now]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v == pa) continue; dfs(v, now); if(vis[now]){ dp[now][1] += min(dp[v][0], dp[v][1] + edge[i].cost); dp[now][0] = oo; }else{ dp[now][0] += min(dp[v][0], dp[v][1] + edge[i].cost); } } if(vis[now]) return; for(int i = head[now]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v == pa) continue; dp[now][1] = min(dp[now][1], dp[now][0] - min(dp[v][0], dp[v][1] + edge[i].cost) + dp[v][1]); } } int main (void) { int T;scanf("%d", &T); while(T--){ tot = 0; memset(head, -1, sizeof(head)); int n, k;scanf("%d%d", &n, &k); int u, v, x; for(int i = 0; i < n - 1; ++i){ scanf("%d%d%d", &u, &v, &x); addedge(u, v, x); addedge(v, u, x); root = u; } memset(vis, false, sizeof(vis)); for(int i = 0; i < k; ++i){ scanf("%d", &v); vis[v] = true; } dfs(root, -1); int ans; printf("%lld\n", min(dp[root][1], dp[root][0])); } return 0; }
|
