【題目敘述】https://vjudge.net/problem/POJ-1251
【參考】ZeroJudge d909: 公路局長好煩惱！？【題解】
【解題想法】最小生成樹 (Minimum Spanning Tree, MST)
- 題目保證 “n-1 lines that start with village labels in alphabetical order”，所以起點的 village label 不需轉換，直接用 i (Line-38)。Line-36 將道路另一端點的 village label 轉換成編號。
- 函式 Find( )：執行並查集的 Find( )。
- Line-51：執行並查集的 Union( )。
- Line-53：使用 n-1 條邊後，就完成最小生成樹了。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge{
int x, y, cost;
};
int n, m, a, b, p[30], ans, cnt;
char c;
vector <edge> v;
edge now;
bool cmp(edge a, edge b){
return a.cost < b.cost;
}
int Find(int x){
if (p[x] == x) return x;
else{
p[x] = Find(p[x]);
return p[x];
}
}
int main(){
while (cin >> n){
if (n == 0) break;
v.clear();
for (int i = 0; i < n-1; i++){
cin >> c;
cin >> m;
for (int j = 0; j < m; j++){
cin >> c;
a = c - 'A'; //終點
cin >> b; //道路維護費用
v.push_back({i, a, b});
}
}
for (int i = 0; i < n; i++){
p[i] = i;
}
sort(v.begin(), v.end(), cmp);
ans = 0;
cnt = n-1; //需要n-1條邊
for (int i = 0; i < v.size(); i++){
now = v[i];
if (Find(now.x) == Find(now.y)) continue;
else{
p[p[now.x]] = p[now.y];
ans += now.cost;
if (--cnt == 0) break;
}
}
cout << ans << "\n";
}
return 0;
}