cgy12306
[백준 BoJ] 6497 - 전력난 본문
// https://www.acmicpc.net/problem/6497
// 전력난
#include<iostream>
#include<vector>
#include<tuple>
#include<cstring>
#include<algorithm>
using namespace std;
int M, N, parent[200001], Msum;
vector<tuple<int, int, int>> city;
bool cmp(tuple<int, int, int> a, tuple<int, int, int> b) {
return get<2>(a) < get<2>(b);
}
int Find(int x) {
if (parent[x] == x) return x;
return parent[x] = Find(parent[x]);
}
void Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void kruskal() {
int sum = 0;
for (auto c : city) {
int a = get<0>(c);
int b = get<1>(c);
int cost = get<2>(c);
if (Find(a) != Find(b)) {
sum += cost;
Union(a, b);
}
}
cout << Msum - sum << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (1) {
cin >> M >> N;
if (M == 0 && N == 0) break;
city.clear();
memset(parent, 0, sizeof(parent));
for (int i = 0; i < M; i++) {
parent[i] = i;
}
Msum = 0;
for (int i = 0; i < N; i++) {
int x, y, z;
cin >> x >> y >> z;
city.push_back(make_tuple(x, y, z));
Msum += z;
}
sort(city.begin(), city.end(), cmp);
kruskal();
}
}
- Minimum Spanning Tree
- 크루스칼
'Algorithm > C++' 카테고리의 다른 글
[백준 BoJ] 1774 - 우주신과의 교감 (0) | 2022.01.19 |
---|---|
[백준 BoJ] 4386 - 별자리 만들기 (0) | 2022.01.19 |
[백준 BoJ] 1647 - 도시 분할 계획 (0) | 2022.01.18 |
[백준 BoJ] 1197 - 최소 스패닝 트리 (0) | 2022.01.18 |
[백준 BoJ] 1922 - 네트워크 연결 (0) | 2022.01.18 |
Comments