# 題目: UVa 11747 - Heavy Cycle Edges
# 題目說明
給一個無向圖,其中有數個點及邊
連通使一點能走到任意點 (以最小的 weight)
求多餘的邊的 weight (會造成 circle 的邊的 weight)
INPUT:
每筆測資第一行有兩個整數 n
和 m
n
代表點的數量m
代表邊的數量
接下來有 m
行,每行有三個整數 u
、 v
、 w
代表 u
點及 v
點間有一條 weight 為 w
的邊
OUTPUT:
輸出會造成 circle 的邊的 weight
如果沒有則輸出 forest
# 解題方法
先將所有點的編號及 weight 存入 edge
接著以 kruskcal
演算法,先對 weight 進行 sort
,再用 union_find
演算法判斷是否可連通
將不能連通的邊依序輸出
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <tuple> | |
#include <algorithm> | |
using namespace std; | |
vector< tuple<int, int, int> > edge; | |
vector<int> parents; | |
vector<int> ranks; | |
bool cmp(tuple<int, int, int> s1, tuple<int, int, int> s2) | |
{ | |
return get<2>(s1) < get<2>(s2); | |
} | |
bool union_find(int u, int v) | |
{ | |
// find root of u and v | |
while (u != parents[u]) u = parents[u]; | |
while (v != parents[v]) v = parents[v]; | |
// circle | |
if (u == v) return false; | |
if (ranks[u] > ranks[v]) parents[v] = u; | |
else if (ranks[v] > ranks[u]) parents[u] = v; | |
else parents[v] = u, ++ranks[u]; | |
return true; | |
} | |
void kruskcal() | |
{ | |
sort(edge.begin(), edge.end(), cmp); | |
bool forest = true; | |
for (auto& [u, v, w] : edge) if (!union_find(u, v)) | |
{ | |
if (!forest) cout << " "; | |
cout << w; | |
forest = false; | |
} | |
if (forest) cout << "forest"; | |
cout << "\n"; | |
} | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int n, m; | |
while (cin >> n >> m, n && m) | |
{ | |
// init | |
edge.clear(); | |
parents.clear(); | |
ranks.assign(n, 0); | |
for (int i = 0; i < n; ++i) parents.emplace_back(i); | |
// store side and weight | |
while (m--) | |
{ | |
int u, v, w; | |
cin >> u >> v >> w; | |
edge.push_back({ u, v, w }); | |
} | |
// kruskcal algorithm | |
kruskcal(); | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%2011747/