[USACO08JAN] Cell Phone Network G

GitHub跳转原题关系图返回列表

设 dp[u][0/1/2] 分别表示 u 放塔、被儿子覆盖、等父亲覆盖的最少塔数，用三状态树形 DP 求树上最小支配集。

OJ: luogu

题目 ID: P2899

难度:普及+/提高

标签:树形DP动态规划树最小支配集

日期: 2026-06-21 05:01

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

在树上的一些节点放信号塔。

一个节点如果自己放了塔，或者与某个放塔节点相邻，就算被覆盖。 要求用最少的塔覆盖整棵树。

思路

先看一个只适合小数据验证的暴力：

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

const int MAXN = 22;

int n;
vector<int> g[MAXN];
int choose_tower[MAXN]; // choose_tower[i] = 0/1，表示第 i 个点不放塔/放塔
int ans;

int calc_tower_count() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_tower[i] == 1) cnt++;
    }
    return cnt;
}

bool check() {
    for (int i = 1; i <= n; i++) {
        bool covered = choose_tower[i] == 1;
        for (size_t j = 0; j < g[i].size(); j++) {
            if (choose_tower[g[i][j]] == 1) {
                covered = true;
                break;
            }
        }
        if (!covered) {
            return false;
        }
    }
    return true;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_tower_count();
            if (ans > value) ans = value;
        }
        return;
    }

    // 第 dep 个点的 01 选择：0 不放塔，1 放塔。
    for (int i = 0; i <= 1; i++) {
        choose_tower[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：枚举哪些点放塔，直接检查是否覆盖整棵树。
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        choose_tower[i] = 0;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ans = n;
    dfs_choose(1);
    cout << ans << '\n';
    return 0;
}

brute.cpp 把每个点看成一个 01 选择：choose_tower[i] = 0/1 表示不放塔或放塔。递归先生成完整选择，叶子节点再检查所有点是否被覆盖，并统计放塔数量。

正解是树上的最小支配集经典 DP。

设：

  • dp[u][0]：u 放塔
  • dp[u][1]：u 不放塔，但已经被儿子覆盖
  • dp[u][2]：u 不放塔，等待父亲覆盖

它们都表示覆盖 u 子树所需的最少塔数。

转移分三种：

DP 转移方程

三种状态分别是“自己放塔 / 被儿子覆盖 / 等父亲覆盖”。 对每个儿子 v，核心转移可以写成：

dp[u][0]=1+∑vmin⁡(dp[v][0],dp[v][1],dp[v][2]) dp[u][0] = 1 + \sum_v \min(dp[v][0], dp[v][1], dp[v][2])
dp[u][2]=∑vmin⁡(dp[v][0],dp[v][1]) dp[u][2] = \sum_v \min(dp[v][0], dp[v][1])

dp[u][1] 需要至少一个儿子放塔：

dp[u][1]=∑vmin⁡(dp[v][0],dp[v][1])+min⁡v(dp[v][0]−min⁡(dp[v][0],dp[v][1])) dp[u][1]=\sum_v \min(dp[v][0],dp[v][1]) + \min_v(dp[v][0]-\min(dp[v][0],dp[v][1]))

  1. u 放塔

    每个儿子都可以：

    • 放塔
    • 被自己的儿子覆盖
    • 等 u 覆盖

  2. u 等父亲覆盖

    这时儿子不能再等 u 覆盖，所以每个儿子只能取：

    • 放塔
    • 被自己的儿子覆盖

  3. u 被儿子覆盖

    必须至少有一个儿子放塔。 这是整个题里唯一需要额外小心的限制。

所以本题本质上就是三状态树形 DP。

代码

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

const int MAXN = 10005;
const int INF = 1e9;

vector<int> g[MAXN];
int n;
int dp[MAXN][3];

void dfs(int u, int fa) {
    dp[u][0] = 1;   // u 放塔
    dp[u][1] = 0;   // u 不放塔，且已被儿子覆盖
    dp[u][2] = 0;   // u 不放塔，等待父亲覆盖

    int sum_min_01 = 0;
    bool has_child = false;
    int extra = INF;

    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) {
            continue;
        }
        has_child = true;
        dfs(v, u);

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

        int best01 = min(dp[v][0], dp[v][1]);
        sum_min_01 += best01;
        extra = min(extra, dp[v][0] - best01);
    }

    if (!has_child) {
        dp[u][1] = INF;
        dp[u][2] = 0;
        return;
    }

    // 至少要有一个儿子放塔，才能覆盖 u。
    dp[u][1] = sum_min_01 + extra;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

复杂度

一次 DFS，时间复杂度 O(N)O(N)，空间复杂度 O(N)O(N)。

总结

树上的“最少选点覆盖所有点”很容易想到最小支配集模型。 一旦把状态拆成“自己放 / 被儿子覆盖 / 等父亲覆盖”，转移就非常标准。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析