BOJ 1647: 도시 분할 계획

#BOJ 1647: 도시 분할 계획

1647번: 도시 분할 계획

#풀이

문제에서 임의의 두집 사이에 경로가 항상 존재한다라는 조건이 있고 유지비의 합을 최소를 출력해야 한다.

이것을 보고 최소 신장 트리 로 풀 수 있다.

 

하지만 문제는 마을을 2개로 쪼개야 하는 문제이다.

 

간단하게 생각하면 최소로 유지를 해야 하니 최소 신장 트리에서 가장 큰 가중치를 갖고 있는 간선을 빼버리면

2개의 마을이 생겨 난다는 걸 알 수 있다.

 

최소 신장 트리의 최소 가중치를 구한 다음 최소 신장 트리에 있는 가장 큰 가중치를 빼면 된다.

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m;
vector<int> p(100001, -1);
vector<tuple<int,int,int>> road;
int find(int x){
	if(p[x] <0)
	return x;
	return p[x] = find(p[x]);
}
bool is_diff(int a, int b){
	int u, v;
	u = find(a);
	v = find(b);
	if(u==v) return 0;
	if(u<=v) p[v] = u;
	else p[u] =v;
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >>n >> m;
	
	for(int i = 0; i <m; i++){
		int w, a, b;
		cin >> a >> b >> w;
		road.push_back({w,a,b});
	}
	sort(road.begin(), road.end());
	
	long long ans = 0;
	int cnt = 0;
	int max = 0;
	for(auto nxt : road){
		int w, a, b;
		tie(w,a,b) = nxt;
		if(!is_diff(a,b)) continue;
		ans += w;
		max = max < w ? w : max;
		cnt++;
		if(cnt== n-1) break;
	
	}
	cout << ans - max<<'\n';
	return 0;
}