您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3586 战场通信阻断：树形 DP + 二分答案

編輯：關於C++

题目大意

树上 n 个节点（n≤1000），1 为根（总指挥），叶子为前线士兵。需切断若干边使所有叶子到根的路径不通。切断边权 ≤ x（设备上限），总权和 ≤ m（设备寿命）。求最小可行 x。无解输出 -1。

树形 DP 判定可行性

固定 x，自底向上 DP：

dp[u]：以 u 为根的子树，阻断所有叶子到 u 路径的最小代价
叶子：dp[u] = m+1（表示必须切断上方边，代价设为 >m）
内部节点：遍历子节点 v，边权 w
- 若 w ≤ x：可选切断此边（代价 w）或切断子树内部（代价 dp[v]），取 min(dp[v], w)
- 若 w > x：无法切断此边，只能 dp[v]（用 m+1 表示不可行）
根节点 dp[1] ≤ m 则 x 可行

二分搜索 x

x ∈ [1, maxEdgeWeight]，二分最小可行值。

C++ 实现

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 1005;
struct Edge { int v, w, next; } edge[MAXN*2];
int head[MAXN], ecnt, n, m, mid, dp[MAXN];

void addEdge(int u, int v, int w) {
    edge[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

void dfs(int u, int fa) {
    bool isLeaf = true;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        isLeaf = false;
        dfs(v, u);
    }
    if (isLeaf) { dp[u] = m + 1; return; }
    dp[u] = 0;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v, w = edge[i].w;
        if (v == fa) continue;
        if (w <= mid) dp[u] += min(dp[v], w);
        else dp[u] += min(dp[v], m + 1);
    }
}

int main() {
    while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
        memset(head, -1, sizeof(head));
        ecnt = 0;
        int maxW = 0;
        for (int i = 1; i < n; ++i) {
            int a, b, w; scanf("%d%d%d", &a, &b, &w);
            addEdge(a, b, w); addEdge(b, a, w);
            maxW = max(maxW, w);
        }
        int lo = 1, hi = maxW, ans = -1;
        while (lo <= hi) {
            mid = (lo + hi) / 2;
            memset(dp, 0, sizeof(dp));
            dfs(1, -1);
            if (dp[1] <= m) { ans = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}