HDU 4738 曹操的橋樑：Tarjan 求割邊（橋）的最小權值

問題建模

給定無向圖，邊有權值（炸毀成本）。圖可能不連通、有重邊。要求：
1. 若原圖不連通 → 輸出 0（無需炸橋）
2. 若連通但無割邊 → 輸出 -1（無法分離）
3. 否則輸出最小割邊權值（至少炸一座橋）

Tarjan 算法核心：低鏈接值

對於無向圖邊 (u, v)，若 low[v] > dfn[u]，則 (u, v) 是割邊。
重邊處理：用邊 ID 而非父節點判斷回溯，避免誤判重邊為割邊。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;

int dfn[N], low[N], dfs_clock;
int n, m;
bool is_bridge[N]; // 邊是否為割邊

struct Edge {
    int to, w, id;
    Edge(int t, int w_, int i) : to(t), w(w_), id(i) {}
};

vector<Edge> g[N];
int ans;

void tarjan(int u, int parent_edge_id) {
    dfn[u] = low[u] = ++dfs_clock;
    for (auto& e : g[u]) {
        int v = e.to;
        if (e.id == parent_edge_id) continue; // 同一條邊的反向
        
        if (!dfn[v]) {
            tarjan(v, e.id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                // (u, v) 是割邊
                ans = min(ans, e.w);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &m) && n) {
        for (int i = 0; i < n; i++) {
            g[i].clear();
            dfn[i] = low[i] = 0;
        }
        dfs_clock = 0;
        
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            u--; v--; // 0-based
            g[u].push_back(Edge(v, w, i));
            g[v].push_back(Edge(u, w, i));
        }
        
        int connected_components = 0;
        ans = INF;
        for (int i = 0; i < n; i++) {
            if (!dfn[i]) {
                connected_components++;
                tarjan(i, -1);
            }
        }
        
        if (connected_components > 1) {
            printf("0\n"); // 原圖不連通
        } else if (ans == INF) {
            printf("-1\n"); // 連通但無割邊
        } else {
            if (ans == 0) ans = 1; // 題目要求至少派一人
            printf("%d\n", ans);
        }
    }
    return 0;
}

關鍵細節總結

• 連通性檢查：DFS 計數連通分量，>1 直接輸出 0
• 重邊處理：記錄邊 ID，遞歸時傳遞 parent_edge_id 而非父節點
• 最小權值：遍歷所有割邊取最小，注意 ans 初值為 INF
• 特殊情況：無割邊輸出 -1；最小權值為 0 時按題意改為 1

這道題是 Tarjan 求割邊的標準應用，重點在於正確處理重邊和圖不連通的邊界情況。