SDOI2006 保安站岗

一道很经典的树形dp题目。

Sol.

很明显的树形dp，先把方程设出来：

\(f_{x,0/1/2}\) 表示当前节点为 \(x\)，\(0(自己覆盖)/1(儿子覆盖)/2(父亲覆盖)\)，且其子节点都已全部覆盖的最小权值。

很套路的树形dp方程，分别考虑如何转移：

记 \(son(i)\) 表示 \(i\) 的所有子节点，\(k_i\) 表示控制 \(i\) 点所需的代价。

1. \(f_{x,0}\)（自己覆盖）

\(f_{x,0} = \sum\limits_{y\in son(x)}\min\{f_{y,0},f_{y,1},f_{y,2}\}+k_x\)

解释：由于当前节点自己覆盖自己，所以不需考虑其他的节点，在所有子节点中找到最小值转移即可。

2. \(f_{x,1}\)（儿子覆盖）

\(f_{x,1} = \sum\limits_{y\in son(x)}\min\{f_{y,0},f_{y,1}\}\)

解释：当当前节点被儿子覆盖时，说明当前节点不可能覆盖儿子节点，也就无法从 \(f_{y,2}\) 转移。

但是有一种这样的情况：当儿子节点全部选择 \(f_{y,1}\) 时，即儿子节点全部被它的儿子节点覆盖，在这种情况下 \(x\) 节点无法被儿子节点覆盖。

所以我们在转移的时候记一个 \(q\) 表示是否全部选择的 \(f_{y,1}\)，如果是，则强制选择一个节点让其选择 \(f_{y,0}\)。我们要向最小化代价，显然要让强制选择的节点 \(f_{y,0}\) 与 \(f_{y,1}\) 的差值最小。所以现在转移方程如下：

\(f_{x,1} = \sum\limits_{y\in son(x)}\min\{f_{y,0},f_{y,1}\},\text{if all choose } f_{y,1},\text{then}+\min\limits_{y\in son(x)}\{f_{y,0}-f_{y,1}\}\)

3. \(f_{x,2}\)（父亲覆盖）

\(f_{x,2} = \sum\limits_{y\in son(x)}\min\{f_{y,0},f_{y,1}\}\)

解释：这个就比较简单了，当当前节点被父亲覆盖，直接从可能的方式转移即可。

Code

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}
    return s * f;
}

const int MAXN = 2000;
const int INF = 1e9 + 7;

struct Edge
{
    int nxt, to;
}e[MAXN << 1];

int head[MAXN << 1], k[MAXN];

int f[MAXN][3];

int n, cnt;

void add_edge(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

void dfs(int x, int fa)
{
    f[x][0] = k[x];
    int sum = 0, minn = INF;
    bool flag = true;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int y = e[i].to;
        if(y == fa) continue;
        dfs(y, x);
        f[x][0] += min(f[y][0], min(f[y][1], f[y][2]));
        f[x][2] += min(f[y][0], f[y][1]);
        int tmp = min(f[y][0], f[y][1]);
        f[x][1] += tmp;
        if(tmp == f[y][0]) flag = false;
        minn = min(minn, f[y][0] - f[y][1]);
    }
    if(flag) f[x][1] += minn;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        int x = read();
        k[x] = read();
        int m = read();
        for(int j = 1; j <= m; j++)
        {
            int y = read();
            add_edge(x, y);
            add_edge(y, x);
        }
    }
    dfs(1, 0);
    printf("%d\n", min(f[1][0], f[1][1]));
    return 0;
}