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;
}