백준 1647번 도시 분할 계획 C++

출처 : https://www.acmicpc.net/problem/1647

 

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리를 구하고 최소 스패닝 트리로 연결된 길 중에서 유지비의 값이 가장 높은 길을 빼면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

struct LoadInfo {
	int start;
	int end;
	int cost;
	bool operator<(const LoadInfo& other) {
		return cost < other.cost;
	}
};

vector<int> parent;
vector<int> height;
vector<LoadInfo> loads;

int GetParent(int n) {
	if (n == parent[n])
		return n;
	return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {

	u = GetParent(u);
	v = GetParent(v);

	if (u == v)
		return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	parent = vector<int>(n + 1);
	height = vector<int>(n + 1, 1);
	for (int i = 1; i <= n; i++)
		parent[i] = i;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		loads.push_back({ start,end,cost });
	}
	sort(loads.begin(), loads.end());
	int sum = 0;
	int maxCost = 0;
	for (int i = 0; i < m; i++) {
		int start = loads[i].start;
		int end = loads[i].end;
		int cost = loads[i].cost;
		if (GetParent(start) == GetParent(end))
			continue;
		Merge(start, end);
		sum += cost;
		maxCost = max(maxCost, cost);
	}
	int ans = sum - maxCost;
	cout << ans;
}