BZOJ 1196 [HNOI2006] 公路修建問題：二分答案 + 並查集求解

問題描述

OI island 有 n 個景點（1 ≤ n ≤ 10000），需修建 n-1 條公路使其連通。公路分一級（費用 c1）與二級（費用 c2，c2 ≤ c1），要求至少 k 條一級公路。目標是在滿足條件下，使最貴公路的費用盡可能小。給定 m 條可建公路（n-1 ≤ m ≤ 20000），求最小可能的最大費用。

解題思路：二分答案 + 並查集判定

對答案（最大費用）進行二分搜尋，範圍 [0, 30000]。對於二分值 x，判定是否能建構滿足條件的生成樹：

1. 優先選擇 c1 ≤ x 的一級公路，統計數量 tot
2. 若 tot < k，直接失敗
3. 再選擇 c1 > x 但 c2 ≤ x 的二級公路
4. 最後用並查集檢查圖是否連通

核心程式碼

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

struct Edge {
    int x, y, c1, c2;
} e[20005];

int f[10005], n, m, k;

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

bool check(int x) {
    int tot = 0;
    for (int i = 1; i <= n; i++) f[i] = i;
    // 先連 c1 <= x 的一級公路
    for (int i = 1; i <= m; i++) {
        int fa = find(e[i].x), fb = find(e[i].y);
        if (fa != fb && e[i].c1 <= x) {
            tot++;
            f[fa] = fb;
        }
    }
    // 再連 c2 <= x 的二級公路
    for (int i = 1; i <= m; i++) {
        int fa = find(e[i].x), fb = find(e[i].y);
        if (fa != fb && e[i].c2 <= x) {
            f[fa] = fb;
        }
    }
    if (tot < k) return false;
    // 檢查連通性
    for (int i = 1; i <= n - 1; i++)
        if (find(i) != find(i + 1)) return false;
    return true;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    m--;
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].c1, &e[i].c2);
    int l = 0, r = 30000;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", r);
    return 0;
}

複雜度分析

• 二分搜尋：O(log 30000) ≈ 15 次
• 每次判定：O(m α(n))，α 為反阿克曼函數
• 總複雜度：O(m log C)，完全滿足限制