poj 3659 Cell Phone Network

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

树dp

1
2
3
4
5
6
7
8
9
10
dp[u][0] : 自己建站,那么选儿子的时候就可以考虑掉3种情况,然后选一个最小的
dp[u][0] = sigma min(dp[v][0] , dp[v][1] , dp[v][2]) + 1
dp[u][1] : 父亲建站,那么选儿子的时候不能包括dp[v][1],因为u这里是没有站的
dp[u][1] = sigma min(dp[v][0] , dp[v][2]);
dp[u][2] : 儿子建站,那么肯定选了一个dp[v][0],但是这里要讨论一个问题
如果存在一个或多个v,满足dp[v][0] < dp[v][2],那么肯定选最小的那个dp[v][0],
其余的可以统一选min(dp[v][0],dp[v][2]),那么总的来说还是 dp[u][2] = sigma min(dp[v][0],dp[v][2]);
但如果不存在,那么只好这样选, delta = dp[v][0] - dp[v][2];选delta最小的,作为那个dp[v][0]
其余的都选min(dp[v][0],dp[v][2]); 这里甚至都不需要比较,其实就是dp[v][2]
因而写成代码就是 dp[u][2] = min(dp[v][0] - dp[v][2]) + sigma min(dp[v][0] , dp[v][2]);
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 10010
#define INF 0x3f3f3f3f
#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){
dp[u][0] = 1;
int delta = INF,sum = 0;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
dp[u][0] += min(dp[v][0],min(dp[v][1],dp[v][2]));
dp[u][1] += min(dp[v][0],dp[v][2]);
if(dp[v][0] - dp[v][2] < delta){
delta = dp[v][0] - dp[v][2];
}
sum += min(dp[v][0],dp[v][2]);
}
if(delta < 0) dp[u][2] = sum;
else dp[u][2] = sum + delta;
}

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);
}
cl(dp,0);
dfs(1,-1);
printf("%d\n",min(dp[1][0],dp[1][2]));
}
return 0;
}