[백준 6497] 전력난 (C++)

문제 링크: https://www.acmicpc.net/problem/6497

6497번: 전력난

1. 주의할 점

- 모든 간선의 총합 - MST를 연결할때 드는 최소 비용을 출력한다

- 매 TC마다 Par[] 배열을 초기화 한다

 

2. 구현

- 크루스칼 알고리즘을 통해 MST를 구현한다

- 입력받는 모든 간선에 대한 정보를 우선순위 큐에 삽입하고, 간선의 가중치가 오름차순이 되도록 정렬한다

- Find_parent(int x) 함수를 통해 X의 부모를 반환한다

- Make_union(int a, int b) 함수를 통해 A와 B의 부모를 통일시킨다(부모의 숫자가 작은 쪽으로)

- 우선순위 큐에서 1개씩 빼면서 간선의 양끝점이 같은 부모를 뒀으면 Continue, 같은 부모가 아니라면 부모를 합치고 해당 간선의 값을 Result에 합친다

- 입력받은 모든 간선 가중치의 합 - Result를 출력한다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int s, e, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, s, e, val;
int par[200000];

int find_parent(int x) {
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) par[b] = a;
	else if (a > b) par[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	while (1) {
		cin >> node >> edge;
		if (node == 0 && edge == 0) break;
		priority_queue<info, vector<info>, cmp> pq;
		long long tot = 0;
		for (int i = 0; i < node; i++)
			par[i] = i;
		for (int i = 0; i < edge; i++) {
			cin >> s >> e >> val;
			tmp.s = s;
			tmp.e = e;
			tmp.val = val;
			pq.push(tmp);
			tot += val;
		}
		long long result = 0;
		while (!pq.empty()) {
			int cs = pq.top().s;
			int ce = pq.top().e;
			int cv = pq.top().val;
			pq.pop();
			int ps = find_parent(cs);
			int pe = find_parent(ce);
			if (ps == pe) continue;
			make_union(cs, ce);
			result += cv;
		}
		cout << tot - result << '\n';
	}
	system("pause");
	return 0;
}