ACM-ICPC Live Archive 2198 Protecting Zonk

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

树dp

题意:给一个无根树,有两种保护,a保护的花费是a,放在一个点,可以保护和它相连的所有边,b保护的花费是b,放在一个点,可以保护到2层的边(即从该点出发路径长度为2的边都能保护,保护能力相当于是a的2倍)。目的是保护所有的边,在一些点上放置a和b保护,使得花费最小

思路参考了Yuan神

这题,有些难想,但其实是想到了不敢下手,因为考虑的方面无非就是,每个点要怎么放,以及放了之后会怎样得到什么样的局面

对于一个点u

  1. A[u]:父边和爷边均被覆盖,u下的子树均被覆盖的最小花费
  2. B[u]:父边被覆盖,u下的子树均被覆盖的最小花费
  3. C[u]:父边不一定被覆盖,但u下子树全部被覆盖的最小花费
  4. D[u]:父边不一定被覆盖,u和一些儿子v的边没有被覆盖全,但所有儿子v下面的子树都被覆盖

A[u],在u点必定放了b保护,所以u下面的子树,怎么放都可以

A[u] = sigma min(A[v],B[v],C[v],D[v]) + b;

B[u],可以在u点放一个a保护,那么下面的子树都可以选择A,B,C

B[u] = sigma min(A[v], B[v], C[v]) + a;

B[u],也可以不再u这个放保护,但是至少一有一个儿子放了b保护,即有一个儿子的状态是A[v],那么选哪个A[v]呢,当然是 delta = min(A[v] - min(A[v], B[v], C[v])); 即选了这个A[v],新增的费用最小B[u] = delta + sigma min(A[v], B[v], C[v]);

C[u]:下面的子树均选A[u],B[u]

C[u] = sigma min(A[u], B[u]);

当如果一个子树选了A[u],那么其实其他子树也是可以选C[u]的,同样的,我们选一个A[v]的条件就是

delta = min(A[v] - min(A[v], B[v], C[v])); 即选了这个A[v],新增的费用最小C[u] = delta + sigma min(A[v], B[v], C[v]);

D[u]:因为有些儿子边没有被覆盖全,所以u这个点,以及任何一个儿子都不可能选A[u], A[v]

D[u] = sigma min(B[v], C[v]);

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

int n,tot,a,b,head[N];
struct edge{
int u,v,next;
}e[2*N];
int A[N],B[N],C[N],D[N];

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

void dfs(int u,int fa){
A[u] = B[u] = C[u] = D[u] = 0;
int resb1 = 0 , resb2 = 0;
int resc1 = 0 , resc2 = 0;
int delta = INF;

for(int k = head[u]; k != -1 ; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
dfs(v,u);
A[u] += min(min(A[v],B[v]) , min(C[v],D[v]));
resb1 += min(min(A[v],B[v]) , C[v]);
resb2 += min(min(A[v],B[v]),C[v]);
resc1 += min(A[v],B[v]);
resc2 += min(min(A[v],B[v]),C[v]);
delta = min(delta , A[v] - min(min(A[v],B[v]),C[v]));
D[u] += min(B[v],C[v]);
}
A[u] += b;
resb1 += a;
resb2 += delta;
resc2 += delta;
B[u] = min(resb1,resb2);
C[u] = min(resc1,resc2);
}

int main(){
while(scanf("%d%d%d",&n,&a,&b)!=EOF){
if(!n && !a && !b) break;
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(min(A[1],B[1]),C[1]));
}
return 0;
}