(백준 6497번 전력난) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)

 

백준 6497번

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

 

MST를 구해서 총 가중치의 합에서 빼면 되는 문제!

MST를 구하기 위해서는 크루스칼 알고리즘을 사용하면 되는데, 크루스칼 알고리즘은 union find와 정렬을 잘 조합한 알고리즘이라서 어렵지 않다!

 

#define  _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int uf[200000];
int find(int a) {
	if (uf[a] < 0) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[b] = a;
	return true;
}

struct Edge {
	int u, v, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

int main() {
	while (1) {
		int m, n; scanf("%d %d", &m, &n);
		if (m == 0 && n == 0) break;

		vector<Edge> edges;
		edges.resize(n);
	
		int total = 0;
		for (int i = 0; i < n; i++) {
			int u, v, w; scanf("%d %d %d", &u, &v, &w);
			edges[i] = { u, v, w };
			total += w;
		}
		sort(edges.begin(), edges.end());
		fill(uf, uf + m, -1);

		int result = 0, cnt = 0;
		for (Edge& e : edges) {
			if (merge(e.u, e.v)) {
				result += e.w;
				if (++cnt == m - 1) break;
			}
		}
		printf("%d\n", total - result);
	}
	return 0;
}