poj 3398 Perfect Service

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

定1为根,得到有根树

每个电脑都要被激活或者作为服务器

假设我们已经知道了最后的最佳方案,那么对于每个电脑

  1. 电脑u作为了服务器
  2. 电脑u不是服务器,它被激活
    1. 它被儿子激活
    2. 它被父亲激活它被儿子激活

对已所有电脑,其实就只有这3种情况

但注意一个最优选择,如果电脑u有1个或多个儿子,而且它是被儿子激活的,那么这些儿子中,只有一个是服务器!

因为没必要选2个儿子v1,v2作为服务器,第2个儿子v2,它作用的点就是u,和v2的所以儿子,那么它的作用被“浪费”了一个点,就是u
完全可以不选v2,而选v2的儿子,这样,v2同样能被覆盖,而且不会造成“浪费”

然后可能会想,可能u有多个儿子,但是这些儿子都没有儿子了(即u没有孙子),那么不选u做服务器的话,u的所有儿子都要选上(否则无法激活它们)

这不是和上面的矛盾吗?这时候要注意,可见不选u作服务器就不是一个最优选择!这种情况就应该选u做服务器的,这才是最佳选择!

根据上面的三种可能设置状态

dp[u][0]:u作为服务器,整个子树都被激活的最小花费

dp[u][1]:u不作为服务器,且其父亲也不是服务器,它被其中一个儿子激活,整个子树的最小代价

dp[u][2]:u不作为服务器,父亲作为服务器,被父亲激活,整个子树的最小代价

状态转移

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

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

dp[u][2] = sum[u] = sigma(dp[v][1]);

注意INF的设置,不用太大(因为这里答案最大就是10000而已),否则会int溢出

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100500
#define MAX 201000
#define INF 10000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int v,next;
}e[MAX];
int dp[N][3];

inline void add(int u,int v){
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int fa){
dp[u][0] = 1; dp[u][1] = INF; dp[u][2] = 0;
for(int k = head[u]; k != - 1; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
dfs(v,u);
dp[u][0] += min(dp[v][0],dp[v][2]);
dp[u][2] += dp[v][1];
}
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
dp[u][1] = min(dp[u][1],dp[u][2] - dp[v][1] + dp[v][0]);
}
}

int main(){
while(scanf("%d",&n)!=EOF){
tot = 0; cl(head,-1);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,-1);
printf("%d\n",min(dp[1][0],dp[1][1]));
int buf;
scanf("%d",&buf);
if(buf == -1) break;
}
return 0;
}