poj 1848 Tree

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:在树上加边,使得每个点在切仅在一个环上,问最少的加边次数,如果无法做到,输出-1。添加的不能是自环,重边,即一个环上的点数至少为3

比较突破常规思维的树dp

dp[u][0]:表示u为根的子树要完成任务,添加的最少边数

dp[u][1]:表示u为根的子树,仅余下u这个点,其余点均完成任务添加的最少边数

dp[u][2]:表示u为根的子树,有一条剩余的链没有属于任何一个环,其他点均完成任务,这条链的点数>=2

sum = sigma(dp[v][0]);

dp[u][1] = sum; //这个最容易转移了,就按照定义来,全部儿子子树均完成,只有自己孤立

dp[u][2] = min( sum - dp[v][0] + min(dp[v][1],dp[v][2]) );

//即点u要和其他点形成一条链,那肯定是跟某个儿子开始,那么先让某个儿子孤立出来,这个儿子可能只是自己孤立出来,所以dp[v][1],可能连带着孤立出一条链dp[v][2],选较小的那个花费,那么其他点都是已经完成任务了,其他点完成任务的总代价就是sum-dp[v][0]; 最终就是让sum-dp[v][0]+min(dp[v][1],dp[v][2]);最小

dp[u][0] = min(sum - dp[v][0] + dp[v][2] + 1);

//即有一个儿子,孤立出了一条链(点数>=2),那么再加上u这个点的话,点数>=3,在这条链上添加1条边就能使这条边成环,而其他节点均已完成任务,代价为 sum - dp[v][0];总代价为sum-dp[v][0] + do[v][2] + 1,当然选最小的花费那个

dp[u][0] = min(sum - dp[v][0] - dp[vv][0] + min(dp[v][1],dp[v][2])+min(dp[vv][1],dp[vv][2]) + 1);

//即选出2个儿子v和vv,v和vv都孤立出来,没有成环,那么至少u,v,vv能形成3个点的链。如果v和vv不是孤立出一个点而是孤立出一条链,那么也不影响了,所以就考虑,是孤立出一个点的花费小一些还是孤立出一条链的花费小一些,所以min(dp[v][1],dp[v][2]);

min(dp[vv][1],dp[vv][2]); 其他点均已完成任务,代价为sum - dp[v][0] - dp[vv][0]; u和v,vv连接需要添加1条边,所以+1
最后当然是选代价最少了

min(sum - dp[v][0] - dp[vv][0] + min(dp[v][1],dp[v][2])+min(dp[vv][1],dp[vv][2]) + 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 110
#define INF 1000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,dp[N][3];
vector<int>e[N];

void dfs(int u,int fa){
int sum = 0,leaf = 1;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
leaf = 0;
sum += dp[v][0];
}
dp[u][1] = sum;

int res = INF;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
res = min(res , sum-dp[v][0]+min(dp[v][1],dp[v][2]));
}
dp[u][2] = res;

res = INF;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
res = min(res , 1+sum-dp[v][0]+dp[v][2]);
}
dp[u][0] = min(dp[u][0] , res);
res = INF;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
for(int j = i+1; j < e[u].size(); j++){
int vv = e[u][j];
if(vv == fa) continue;
res = min(res , 1+sum-dp[v][0]-dp[vv][0]+min(dp[v][1],dp[v][2])+min(dp[vv][1],dp[vv][2]));
}
}
dp[u][0] = min(dp[u][0],res);
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
e[i].clear();
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
for(int i = 1; i <= n; i++)
for(int j = 0; j < 3; j++)
dp[i][j] = INF;
dfs(1,-1);
printf("%d\n",((dp[1][0] >= INF) ? (-1) : (dp[1][0])));
}
return 0;
}