题意:给n个顶点,和n-1条边(一颗生成树)。然后给定k个点,表示这些点上有一个机器人。最后让你删去一些边使任意两个机器人都不能互达,且所删边的权值之和要最小。http://acm.hdu.edu.cn/showproblem.php?pid=4313
解:
首先可以看出两个无需决策的选择。
1.如果根节点是危险点,那么其子树中就不能有危险点。
dp[u][0]: 与u连通的子孙结点中没有危险结点时不需要和上面断,需要删除的最小边权值,若u为危险结点,则该值为无穷大。
dp[u][1]:与u连通的子孙结点中有危险结点时需要和上面断,删除的最小边权值。
将以u为根节点的子树看成是个叶子节点,这样好理解一点。
如果i是叶子节点:如果i为危险点dp[i][0] = inf,dp[i][1]= 0;否则dp[i][0] = dp[i][1] = 0;
如果i不是叶子节点:如果i是危险点dp[i][0] = inf , dp[i][1] = sigma min(dp[son][0],dp[son][1]+w);
否则dp[i][0] = sigma min(dp[son][0],dp[son][1]+w),dp[i][1] = min(dp[i][0] – min(dp[son][0],dp[son][1]+w)+dp[son][1])。
我表示我已经很Orz了,做不出来,看一天了也没看懂。感觉不能在这题上纠结下去了,于是就沾了代码。
#include <cstdio> #include <cstring> const int MAXN = 100005; const __int64 INF = 10000000000000000LL; __int64 dp[MAXN][2]; int n, k; struct Edge { int v, w, next; }edge[MAXN * 2]; int edgeNumber, head[MAXN]; bool haveMachine[MAXN]; inline void addEdge(int u, int v, int w) { edge[edgeNumber].v = v; edge[edgeNumber].w = w; edge[edgeNumber].next = head[u]; head[u] = edgeNumber ++; } inline __int64 min(const __int64 &x, const __int64 &y) { return x < y ? x : y; } void dfs(int u, int father) { if(haveMachine[u]) { dp[u][0] = INF; dp[u][1] = 0; } else { dp[u][0] = 0; dp[u][1] = INF; } __int64 minS = INF; __int64 count = 0; for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; int w = edge[i].w; if(v != father) { dfs(v, u); if(haveMachine[u]) { dp[u][1] += min(dp[v][0], dp[v][1] + w); } else { dp[u][0] += min(dp[v][0], dp[v][1] + w); ++ count; if(dp[v][0] <= dp[v][1] + w) { if(minS > dp[v][1] - dp[v][0]) { minS = dp[v][1] - dp[v][0]; } } else { if(minS > - w) { minS = - w; } } } } } if(!haveMachine[u] && count) { dp[u][1] = dp[u][0] + minS; } } int main() { int t; int x, y, z; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &k); edgeNumber = 0; memset(head, -1, sizeof(head)); for(int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&z); addEdge(x, y, z); addEdge(y, x, z); } memset(haveMachine, false, sizeof(haveMachine)); for(int i=0;i<k;++i) { scanf("%d", &x); haveMachine[x] = true; } dfs(0, -1); if(haveMachine[0]) { printf("%I64d\n", dp[0][1]); } else { printf("%I64d\n", min(dp[0][0], dp[0][1])); } } return 0; }
于是,又看,总算有点懂了,这是另一个我看得懂的代码。里面有注释,看了注释你就豁然开朗了。
这里再次鸣谢city。 树dp的要旨是递归到u的时候只考虑u和u的son,不考虑其他。这样子我就懂了。
假设u有5个孩子,两个危险。 对于外面来说,怎样的u这棵子树才是安全的呢?将所有危险边都断掉。
怎样才算不安全的呢,只断掉一条边。(注意,对于u这棵子树内部来说,一定是安全的,因为当u为一个叶子的时候,无论u是危险还是不危险的,肯定是对自己是无伤害的)。
然后这么想很容易就能想通了。
#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; const __int64 inf = 1e13; const int N = 111111; __int64 dp[N][2];//dp[i][0]表示这颗子树不用和上面断 //dp[i][1]表示需要和上面断 int is[N]; vector<pair<int, int> >v[N]; inline __int64 min(__int64 a, __int64 b) { return a<b?a:b; } void dfs(int u, int pre) { int len = v[u].size(); if(is[u]) { dp[u][0] = inf;//这是不可能=- dp[u][1] = 0; } else { dp[u][0] = 0; dp[u][1] = 0; } for(int i=0; i<len; i++){ int vv = v[u][i].first; if(vv == pre) continue; dfs(vv, u); __int64 w = v[u][i].second; //就是这里这么短,但是不懂。。。 //dp[i][0]表示这颗子树不用和上面断,所以这棵子树是安全的 //dp[i][1]表示需要和上面断 __int64 t1 = dp[vv][1]; __int64 t0 = min(t1 + w, dp[vv][0]);//要这条边或者不要这条边的最小值,这样都是安全的 if(is[u]){ dp[u][1] += t0;//怎么地都要和上面断的,应该取个最小值就行,但是u的子树应该是安全的。 //不和上面断是不可能的。 }else{ //到这条边为止, 和之前的边有关系。 //要想变成危险的,或者是之前u是安全的,现在子树是不安全的, //或者是之前u是不安全的,现在子树是安全的。 dp[u][1] = min(dp[u][0] + t1 , dp[u][1] + t0); //如果想变成安全的,必须一致都是安全的。 dp[u][0] += t0; } } } int main() { int t, n, k; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &k); for(int i=0; i<n; i++) v[i].clear(); for(int i=1; i<n; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); v[a].push_back(make_pair(b, c)); v[b].push_back(make_pair(a, c)); } memset(is, 0, sizeof(is)); for(int i=0; i<k; i++) { int a; scanf("%d", &a); is[a] = 1; } dfs(0, -1); __int64 ans = dp[0][0]; if(dp[0][1]<ans) ans = dp[0][1]; cout<<ans<<endl; } return 0; }