컴퓨터 N를 최소의 비용으로 연결하기 위해서는 사이클이 생성되도록 연결하면 번복된 연결이 발생하므로
사이클이 발생하지 않도록 모든 컴퓨터들이 연결되도록 하는 문제로 이해했다.
입력 -> 정점 V1, V2 가중치 W로 vector에 적재하여 가중치 w를 기준으로 오름차순 정렬을 한뒤에
Disjoint_Set을 사용하여 사이클 발생여부를 판단하면서 가중치를 더해주면 끝
Disjoint_Set이나 Mst를 숙지하고 있다면 굉장히*3 쉽게 풀수 있는 문제입니다.
https://www.acmicpc.net/problem/1922
<code>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | // pda_pro12 #include<iostream> #include<vector> #include<algorithm> #define MAX 0x7fff0000 #define N_ 100000 using namespace std; int n, m, par[N_], ans; vector<pair<int, pair<int, int>>> v; int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } bool Merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; par[y] = x; return true; } int main() { int v1, v2, w; ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; i++) par[i] = i; while (m--) { cin >> v1 >> v2 >> w; v.push_back({ w, {v1, v2}}); } sort(v.begin(), v.end()); // 가중치 별 정렬 for (int i = 0; i < v.size(); i++) { int w = v[i].first; int v1 = v[i].second.first; int v2 = v[i].second.second; if (Merge(v1, v2)) // 사이클 발생하지 않을경우 연결 후 ans += w; // 연결비용 적재 } cout << ans; return 0; } |