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

POJ 2075 Tangled in Cables：最小生成樹 (Kruskal + Map) 實戰解析

編輯：關於C++

問題背景

小鎮有 N 戶人家，M 條可鋪設纜線的路徑，每條路徑有長度。現有一卷固定長度的纜線，需判斷能否連通所有房屋，若能則輸出最短所需長度（保留 0.1 英里），否則輸出 "Not enough cable"。經典最小生成樹 (MST) 應用場景。

算法選型：Kruskal + 並查集 + Map 映射

房屋名稱為字符串，需 map<string, int> 映射為整數索引
邊按權值升序排序
並查集檢測環、合併集合
邊數達到 N-1 時停止，累加權值即為 MST 總長

關鍵代碼實現

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

const int MAX = 10000;
int fa[MAX];
struct Edge { int u, v; double w; } e[MAX];
map<string, int> mp;

bool cmp(Edge a, Edge b) { return a.w < b.w; }

void UF_set() { for (int i = 0; i < MAX; i++) fa[i] = i; }
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Union(int a, int b) {
    int r1 = Find(a), r2 = Find(b);
    if (r1 != r2) fa[r2] = r1;
}

double Kruskal(int n, int m) {
    UF_set();
    sort(e, e + m, cmp);
    double res = 0; int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (Find(e[i].u) != Find(e[i].v)) {
            Union(e[i].u, e[i].v);
            res += e[i].w;
            if (++cnt >= n - 1) break;
        }
    }
    return res;
}

int main() {
    double totalLen; int n, m;
    while (scanf("%lf", &totalLen) == 1) {
        scanf("%d", &n);
        mp.clear(); int idx = 1;
        string name;
        for (int i = 0; i < n; i++) {
            cin >> name;
            if (!mp[name]) mp[name] = idx++;
        }
        scanf("%d", &m);
        string a, b; double dist;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> dist;
            e[i].u = mp[a]; e[i].v = mp[b]; e[i].w = dist;
        }
        double need = Kruskal(n, m);
        if (need < totalLen) printf("Need %.1f miles of cable\n", need);
        else printf("Not enough cable\n");
    }
    return 0;
}

樣例解析

輸入:
100.0
4
Jones Smiths Howards Wangs
5
Jones Smiths 2.0
Jones Howards 4.2
Jones Wangs 6.7
Howards Wangs 4.0
Smiths Wangs 10.0

輸出:
Need 10.2 miles of cable

MST 選擇邊：Jones-Smiths (2.0)、Jones-Howards (4.2)、Howards-Wangs (4.0)，總長 10.2 ≤ 100.0，滿足條件。