[백준 알고리즘] 1647번 도시 분할 계획

 

최소 스패닝 트리를 알고 있으면 쉽게 풀 수 있는 문제이다.

두 집 사이에 경로가 있으면 길을 없앨 수 있고, 유지비용을 최소로 하도록 도시를 분할한다.

따라서, 최소 스패닝 트리를 구한 후, 최대의 유지비용이 드는 경로를 없애면 

유지비용이 최소인 도시 분할 방법을 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, pair<int, int>>> edge;
vector<int> parent;

int find_root(int x){
	if(parent[x] == x)
		return x;
	else
		return parent[x] = find_root(parent[x]);
}

void union_root(int x, int y){
	x = find_root(x);
	y = find_root(y);

	if(x != y){
		parent[y] = x;
	}
}

int main(){
	int n,m;

	cin >> n >> m;

	for(int i=0; i<n; i++){
		parent.push_back(i);
	}

	int a,b,c;

	for(int i=0; i<m; i++){
		cin >> a >> b >> c;
		edge.push_back(make_pair(c,make_pair(a-1, b-1)));
	}

	sort(edge.begin(), edge.end());

	int count = 0, answer = 0;
	for(int i=0; i < edge.size(); i++){
		a = edge[i].second.first;
		b = edge[i].second.second;
		c = edge[i].first;

		if(find_root(a) != find_root(b)){
			answer += c;
			union_root(a,b);
			count ++;
			if(count == n-1){
				answer -= c;
				break;
			}
		}
	}

	cout << answer;

	return 0;
}