题解 P2899 【[USACO08JAN]手机网络Cell Phone Network】

loceaner

2019-10-25 11:00:16

Solution

### 题意 $n$个点,$n-1$条边(这就告诉我们这是一棵树),一个点染色可以传递给相邻的结点(也就是说相邻结点相当于被染色了)并将这些相邻结点覆盖,问最少染多少个结点可以完全覆盖这$n$个结点 ### 做法 首先,这是一道**树形DP**基础题 那么,我们考虑一个结点可以被谁染色,不难想出,可以有$3$种情况:被自己染色,被儿子染色,被父亲染色 我们用$f[i][0/1/2]$分别表示$i$这个结点被自己/儿子/父亲染色的最小染色数,即用$f[i][0]$表示自己对自己染色了,用$f[i][1]$表示自己被儿子染色了,用$f[i][2]$表示自己被父亲染色了 那么就可以推出三种状态,我们设目前结点为$u$,他的儿子结点为$v$ #### $1.$**自己被自己染色** 这时我们可以想一下,$u$被自己染色可以由什么转移过来,如果$u$已经被自己染色了的话,他的儿子$v$可以选择自己染色,也可以选择被自己($v$)的儿子染色,当然也可以被$u$染色,当然,我们要选最小的,所以转移方程就是 $$f[u][0] += \min (f[v][0], f[v][1], f[v][2])(v \in son_u)$$ #### $2.$**被自己的父亲结点染色** 如果被父亲结点($fa$)染色了,那么$u$的儿子$v$只能选择自己染色或者被它的儿子染色,转移方程为 $$f[u][0] += \min (f[v][0], f[v][1])(v\in son_u)$$ #### $3.$**被自己的儿子结点染色** 这是最麻烦的一种情况,因为$u$可能有多个儿子,只要有一个儿子自己染色了,就可以将$u$覆盖,这种情况就成立了 而现在它的儿子有两种情况,分别是自己染色和被它儿子染色 我们可以先假设每个儿子都是被它自己染色($v$被自己染色)的,然后看一下$u$的每个儿子($v$)被其儿子染色是否使结果变得更小,把能让结果更小的 自己染色($v$自己染色)的儿子 替换为 被其儿子染色的儿子($v$被它儿子染色)的儿子 (参考了$ysner$大佬的思路) 那么怎么实现呢? 1. 先让$f[u][1]$加上所有的$f[v][0]$(也就是假设所有的$v$目前都是自己给自己染色的) 2. 在进行一的同时,用一个$g$数组,表示$v$被儿子染色所需的价值减去$v$被自己染色的价值的差值,同时用一个变量$tot$记录一下一共有多少个儿子,即$g[++tot] = f[v][1] - f[v][0]$ 3. 如果$u$没有儿子,即$tot$为$0$,说明$u$是一个叶结点,那么就没有从儿子来的价值,因为转移的时候我们要取小的,所以就把$f[u][1]$设为一个极大值 4. 如果$u$有儿子,就将$g$从小到大排序,如果是负值,我们就可以替换,因为是负值的话就说明,此时的$f[v][1]$比$f[v][0]$小,所以就可以替换,只要是负的,值越小越好,所以就排序一下,是负的就替换,否则就$break$,当然我们最多替换$tot-1$个,因为要保证$u$被染色,必须有一个儿子是自己染色的 至此主要部分就讲完了,需要注意的是每次$dfs$的时候先将$f[u][0]$设为$1$,因为自己给自己染色肯定至少为$1$ 然后我们就做完啦~~ ### 代码 ```cpp #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1; for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); return x * f; } const int M = 1e5 + 11; const int INF = 1e9 + 17; int n, m; int f[M][3];//f[i][0/1/2]0表示被自己染了,1表示被儿子染了,2表示被父亲染了 struct node { int nxt, to; } e[M]; int head[M], cnt; inline void add(int from, int to) { e[++cnt].to = to; e[cnt].nxt = head[from]; head[from] = cnt; } bool cmp(int x, int y) { return x > y; } void dfs(int u, int fa) { int tot = 0, g[M]; f[u][0] = 1; for(int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if(v == fa) continue; dfs(v, u); f[u][0] += min(f[v][0], min(f[v][1], f[v][2])); f[u][2] += min(f[v][0], f[v][1]); f[u][1] += f[v][0]; g[++tot] = f[v][1] - f[v][0]; } if(!tot) f[u][1] = INF; else { sort(g + 1, g + 1 + tot); for(int i = 1; i < tot; i++) { if(g[i] < 0) f[u][1] += g[i]; else break; } } return; } int main() { n = read(); for(int i = 1; i < n; i++) { int x = read(), y = read(); add(x, y), add(y, x); } dfs(1, 0); printf("%d", min(f[1][0], f[1][1])); return 0; } ``` 完结撒花qwq