취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6497번 문제인 전력난이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/6497 

주어지는 그래프는 연결그래프이므로, MST(Minimum Spanning Tree; 최소 신장 트리)에 해당하는 가로등을 켜는 데에 사용해야하는 비용이 필요한 최소 비용이고, 따라서 MST를 이루지 않는 모든 도로의 가로등을 끄면 최대로 비용을 절약할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int uf[200000];

int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<pair<int,pair<int, int>>> edges;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, M; cin >> N >> M;
	while (N) {
		int ans = 0;
		for (int i = 0; i < N; i++) uf[i] = i;
		edges.clear();
		while (M--) {
			int x, y, d; cin >> x >> y >> d;
			edges.emplace_back(make_pair(d, make_pair(x, y)));
			ans += d;
		}

		sort(edges.begin(), edges.end());
		for (auto e : edges) {
			int d = e.first, x = e.second.first, y = e.second.second;
			x = findf(x), y = findf(y);
			if (x == y) continue;
			uf[y] = x;
			ans -= d;
		}

		cout << ans << '\n';
		cin >> N >> M;
	}
}