「Luogu P2016」战略游戏

Description

给定一棵 $n\ (1 \leq n \leq 1500)$ 个点的树，编号为 $0 \sim n - 1$，现在需要从中选择若干个点，每个点可以覆盖所有连向它的边，求覆盖所有边至少需要几个点。

Source

[Luogu]P2016

Solution

考虑用 树形DP 求解。

状态：

用 $f_{0,u}$ 表示在节点 $u$ 的子树中，覆盖所有边但不选节点 $u$ 最少需要几个点；

用 $f_{1,u}$ 表示在节点 $u$ 的子树中，覆盖所有边且选了节点 $u$ 最少需要几个点。

初始：

无

转移：

$$\large { f_{0,u} = \sum\limits_{v \in son_u} f_{1,v} }$$

若不选节点 $u$，则节点 $u$ 的儿子 $v$ 必须选，这样才能覆盖到边 $u \rightarrow v$ 。

$$\large { f_{1,u} = \sum\limits_{v \in son_u} \min \left(f_{0, v} , f_{1, v} \right) + 1 }$$

若选节点 $u$，则边 $u \rightarrow v$ 一定能被覆盖，节点 $v$ 可选可不选，显然取节点 $v$ 选 和 不选 的较小值更优，并加上 $1$（算上节点 $u$）。

答案：

$$\large{\begin{aligned} &\min \left(f_{0,root},f_{1,root} \right) && (root\ 表示根节点) \end{aligned}}$$

考虑在根节点的子树中（整棵树），根节点 选 或 不选，取较小值即是答案。因为本题没有给出根节点，所以直接设 $1$ 号节点为根，连无向边即可。

时间复杂度为 $O(n)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1500, MAXM = 1500;
int n, tot, head[MAXN + 5], f[2][MAXN + 5];
struct Edge {
    int next, to;
} e[(MAXM << 1) + 5];

inline void addEdge(int u, int v) {
    e[++tot] = (Edge) { head[u], v };
    head[u] = tot;
}

void dfs(int u, int fa) {
    f[1][u] = 1;
    for (int v, i = head[u]; v = e[i].to, i; i = e[i].next) {
        if (v == fa) continue;
        dfs(v, u);
        f[0][u] += f[1][v];
        f[1][u] += min(f[0][v], f[1][v]);//转移
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        int u, v, k;
        read(u);
        ++u;//习惯点的编号从 1 开始
        for (read(k); k; --k) {
            read(v);
            ++v;
            addEdge(u, v), addEdge(v, u);//连无向边
        }
    }
    dfs(1, 0);//设根节点为 1 号节点
    write(min(f[0][1], f[1][1]));
    putchar('\n');
    return 0;
}