題意#
世界上有 \(n\) 座城市以及 \(m\) 條年久失修的道路。這些道路實在太爛了，已經完全沒辦法走。為了讓所有城市之間能夠再次順利通行（彼此互相連通），我們必須挑選一部分的道路來進行修補。
每條道路修補的報價各不相同。你的任務是評估出：在保證所有城市都能互通的最低底線下，修路的總花費「最少」可以壓到多少？如果再怎麼修都沒辦法將所有城市打通，請輸出 IMPOSSIBLE。
思路#
看到「所有城市打通」還要「總花費最少」，連想都不用想，這絕對是一道最標準的「最小生成樹（Minimum Spanning Tree, MST）」裸題。
要求 MST，我們最常用的武器就是 Kruskal’s Algorithm，它的實作方式非常暴力且直覺，基本上就是「貪婪法」與「互斥集（DSU）」的完美結合：
- 首先把所有可以修補的道路，依照報價「從便宜到貴」排序。
- 接著我們從最便宜的道路開始一一檢視。只要這條路連著的兩個城市「目前還沒有互通」（可以透過 DSU 輕鬆判定），我們就毫不猶豫地花錢把它修好，讓這兩個區塊合體！
- 若這條路兩端的城市根本就已經屬於同一個互通網路了，那就直接無視它，把錢省下來。
就這樣一路掃過去，當所有邊都檢查完，我們挑出來的路徑就會是成本最完美的組合。最後還要防雷一下，確認我們合併出來的連通塊是不是真的只剩下一個（包含所有城市），這時就能安心印出最少的修路花費了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
#define TIII tuple<int, int, int>
vector<int> anc; // DSU 集合老大記錄
// 互斥集 Find 操作：尋找最終老大，附帶路徑壓縮
int Find(int x) {
return x == anc[x] ? x : anc[x] = Find(anc[x]);
}
// 互斥集 Union 操作：合併兩個集合。如果原本就不相連就合併並回傳 true，否則 false
bool Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return false;
if (a > b) swap(a, b);
return anc[b] = a, true;
}
signed main() { WA();
int n, m; cin >> n >> m;
// 初始化 DSU 陣列，1-based 因此開到 n+1，預設每人都是自己的老大
anc.assign(n+1, 0);
iota(all(anc), 0);
// 讀入所有邊，儲存格式為 {cost, cityA, cityB} 以便等等排序
vector<TIII> g;
while (m--) {
int a, b, w; cin >> a >> b >> w;
g.pb({w, a, b});
}
// 貪心策略：依花費由小到大排序
sort(all(g));
int ans = 0;
// 依序檢視便宜的邊，如果能有效擴張連通塊（Union 回傳 true），就將花費累加上去
for (auto &[w, a, b] : g) if (Union(a, b)) ans += w;
// 統計最終這張圖剩下了幾個連通塊的源頭
set<int> st;
for (auto &i : anc) st.insert(Find(i));
// 因為索引 0 並沒有被拿來使用而自成一格，因此若全部相連，集合數量應該為 2
if (st.size() == 2) cout << ans << '\n';
else cout << "IMPOSSIBLE\n"; // 還有未連通的孤島
}
