HDU 4738：曹操的橋 - 求最小割橋 (Tarjan 算法)

問題描述

給定無向圖（島嶼與橋），每座橋有守衛數 W。周瑜僅能炸毀一座橋，且派出的士兵數必須 ≥ 該橋守衛數。求使圖不連通所需的最小士兵數。若原圖不連通輸出 0；若無割橋輸出 -1；若最小割橋守衛數為 0 輸出 1。

核心思路：Tarjan 求割橋

無向圖中，邊 (u, v) 是割橋 ⇔ 在 DFS 樹中 low[v] > dfn[u]（假設 u 是 v 的父節點）。

步驟：

1. 用 Tarjan 算法找出所有割橋。
2. 若圖原本不連通（並查集判斷），輸出 0。
3. 在所有割橋中找最小守衛數 minW。
4. 根據 minW 輸出：minW == 0 ? 1 : (minW == INF ? -1 : minW)。

代碼實現 (關鍵部分)

struct Edge { int to, next, w; bool isBridge; } e[MAXM];
int head[MAXN], dfn[MAXN], low[MAXN], idx, bridgeCnt;
int n, m;

void tarjan(int u, int parentEdge) {
    dfn[u] = low[u] = ++idx;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) { // 割橋
                e[i].isBridge = e[i^1].isBridge = true;
                bridgeCnt++;
            }
        } else if (i != (parentEdge ^ 1)) { // 非父邊
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    while (scanf("%d%d", &n, &m), n || m) {
        // 初始化、建圖、並查集判連通
        // ...
        tarjan(1, -1);
        int minW = INF;
        for (int u = 1; u <= n; ++u)
            for (int i = head[u]; ~i; i = e[i].next)
                if (e[i].isBridge)
                    minW = min(minW, e[i].w);
        if (!connected) puts("0");
        else if (minW == 0) puts("1");
        else if (minW == INF) puts("-1");
        else printf("%d\n", minW);
    }
    return 0;
}

注意事項

• 重邊處理：Tarjan 標準模板中，parentEdge 參數避免將雙向邊誤判為回邊。
• 並查集預判連通性，避免孤立島嶼導致誤判。
• 守衛數為 0 的割橋，派 1 人即可（題目要求士兵數 ≥ 守衛數，且至少派 1 人）。

總結

本題是「最小割橋」的直接應用，結合 Tarjan 找橋與並查集判連通，屬於圖論基礎必會題型。