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

HDU 4005 The War - 雙連通分量縮點與樹上最小割

編輯：C++ 入門

HDU 4005 The War - 雙連通分量縮點與樹上最小割

問題描述

給定一個連通無向圖，每條邊有炸毀代價。敵方將添加一條未知邊，你需要預先決定最小代價，使得無論敵方在哪裡添加邊，你都能炸毀若干邊讓圖不連通。

核心觀察

要斷開連通圖，必須炸毀橋 (bridge)
先進行 雙連通分量縮點，得到一棵樹（橋樹）
樹上的每條邊對應原圖的一座橋
敵方添加邊會在樹上形成一個環
你需要炸毀環上代價最小的橋

解題策略

Tarjan 算法找所有橋 (割邊)
縮點構建橋樹：每個雙連通分量為一個節點，橋為樹邊
在橋樹中找權值最小的邊 (minEdge)
從 minEdge 的兩端點出發 DFS，尋找兩條不相交路徑，使得它們與 minEdge 形成一個環
答案 = 除這個環以外的所有橋中權值最小者

關鍵洞察

敵方添加邊會連接樹上的任意兩點 u, v，形成唯一路徑構成的環。你必須炸毀環上的一條橋。為了保證最小代價，你需要確保每個可能的環都包含全局最小橋。這等價於：找到一個包含最小橋的環，使得環外最小橋最大化（即環內包含盡可能多的小橋）。

實際操作：從最小橋的兩端點分別 DFS，每個子樹維護兩條最小路徑，合併時更新答案。

完整 C++ 代碼

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

const int N = 10005;
const int M = 200005;
const int INF = 0x3f3f3f3f;

int n, m;
struct Edge {
    int u, v, val, id;
    bool iscut;
    Edge() {}
    Edge(int u, int v, int val, int id) : u(u), v(v), val(val), id(id), iscut(false) {}
} edge[M];

int en, first[N], nxt[M];

void init() {
    en = 0;
    memset(first, -1, sizeof(first));
}

void add_edge(int u, int v, int val, int id) {
    edge[en] = Edge(u, v, val, id);
    nxt[en] = first[u];
    first[u] = en++;
}

int pre[N], dfn[N], dfs_clock, bccn, bccno[N];
vector<Edge> bcc[N];

// Tarjan 找橋
void dfs_cut(int u, int id) {
    pre[u] = dfn[u] = ++dfs_clock;
    for (int i = first[u]; i != -1; i = nxt[i]) {
        if (edge[i].id == id) continue;
        int v = edge[i].v;
        if (!pre[v]) {
            dfs_cut(v, edge[i].id);
            dfn[u] = min(dfn[u], dfn[v]);
            if (dfn[v] > pre[u]) 
                edge[i].iscut = edge[i^1].iscut = true;
        } else {
            dfn[u] = min(dfn[u], pre[v]);
        }
    }
}

void find_cut() {
    dfs_clock = 0;
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++) 
        if (!pre[i]) dfs_cut(i, -1);
}

// 縮點
void dfs_bcc(int u) {
    bccno[u] = bccn;
    for (int i = first[u]; i != -1; i = nxt[i]) {
        if (edge[i].iscut) continue;
        int v = edge[i].v;
        if (bccno[v]) continue;
        dfs_bcc(v);
    }
}

Edge Mine;

void find_bcc() {
    bccn = 0;
    memset(bccno, 0, sizeof(bccno));
    for (int i = 1; i <= n; i++) 
        if (!bccno[i]) { bccn++; dfs_bcc(i); }
    
    for (int i = 1; i <= bccn; i++) bcc[i].clear();
    Mine.val = INF;
    
    for (int i = 0; i < en; i++) {
        if (!edge[i].iscut) continue;
        if (Mine.val > edge[i].val) Mine = edge[i];
        int u = bccno[edge[i].u], v = bccno[edge[i].v], w = edge[i].val;
        bcc[u].push_back(Edge(u, v, w, 0));
    }
}

// 樹上 DFS 維護兩條最小路徑
int ans;

int dfs(int u, int f) {
    int min1 = INF, min2 = INF;
    for (int i = 0; i < bcc[u].size(); i++) {
        int v = bcc[u][i].v;
        if (v == f) continue;
        int childMin = dfs(v, u);
        min2 = min(min(childMin, bcc[u][i].val), min2);
        if (min2 < min1) swap(min1, min2);
    }
    ans = min(ans, min2);
    return min1;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        init();
        int u, v, w;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            if (u > n || v > n) continue;
            add_edge(u, v, w, i);
            add_edge(v, u, w, i);
        }
        
        find_cut();
        find_bcc();
        
        if (bccn == 1) {  // 原圖無橋，已是雙連通
            printf("-1\n");
            continue;
        }
        
        ans = INF;
        int u = bccno[Mine.u], v = bccno[Mine.v];
        dfs(u, v);
        dfs(v, u);
        
        if (ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}