POJ 1251 Jungle Roads：最小生成樹 Kruskal 模板

題目大意

• 村莊標號 A..I（≤ 26），道路帶維護成本。
• 輸入格式：每行 `V k U1 C1 U2 C2 ...` 表示從 V 到後續字母村莊的道路。
• 求連通所有村莊的最小維護成本（MST 權重和）。

Kruskal 算法

1. 解析輸入，構建邊列表 `(u, v, w)`。
2. 按權重升序排序。
3. 並查集維護連通分量，遍歷邊，若兩端點不在同一集合則合併並累加權重。
4. 邊數達到 `n-1` 可提前結束。

完整代碼

#include 
using namespace std;
struct Edge { int u, v, w; };
int find(vector& p, int x) { return p[x] == x ? x : p[x] = find(p, p[x]); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        vector edges;
        for (int i = 0; i < n-1; ++i) {
            char v; int k; cin >> v >> k;
            for (int j = 0; j < k; ++j) {
                char u; int w; cin >> u >> w;
                edges.push_back({v - 'A', u - 'A', w});
            }
        }
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
        vector p(n); iota(p.begin(), p.end(), 0);
        int ans = 0, cnt = 0;
        for (auto& e : edges) {
            int fu = find(p, e.u), fv = find(p, e.v);
            if (fu != fv) {
                p[fu] = fv;
                ans += e.w;
                if (++cnt == n-1) break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 排序 O(E log E)，`E ≤ 75`。
• 並查集 O(E α(V))，極快。