백준 1647번: 도시 분할 계획
도시 분할 계획
아이디어
트리가 만들어지면 간선이 총 N-1개이다. MST를 만들다 간선의 개수가 N-2가 되었을 때 멈춘다면 도시가 최소의 비용으로 분할된다.
코드
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 100001;
int N, M;
int p[MAX];
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void merge(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
p[n1] += p[n2];
p[n2] = n1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
vector<pair<int, pair<int, int>>> v;
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
v.push_back({c, {a, b}});
}
sort(v.begin(), v.end());
memset(p, -1, sizeof(p));
int cnt = 0, ans = 0;
for (auto p : v) {
int c = p.first;
int a = p.second.first;
int b = p.second.second;
if (find(a) == find(b)) continue;
ans += c;
cnt++;
merge(a, b);
if (cnt == N-2) break;
}
cout << ans << '\n';
return 0;
}
여담
즐거운 MST
Author And Source
이 문제에 관하여(백준 1647번: 도시 분할 계획), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-1647번-도시-분할-계획저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)