[1922번] 네트워크 연결

1922번: 네트워크 연결

 

www.acmicpc.net

Union Find를 이용해 풀 수 있는 쉬운 문제

입력 받은 경로들의 비용을 기준으로 정렬해서 차례대로 Union을 진행한다.

Union할 수 있을 때 비용들을 누적해서 최종적으로 출력하면 된다.

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

/*1922번 네트워크 */ #include <iostream> #include <algorithm> #define SIZE 1001 using namespace std; struct info {     int s, e, value; }V[100000];   bool cmp(const info &a, const info &b) {     if (a.value < b.value) return true;     else if (a.value == b.value) return a.s < b.s;     else return false; }   int parent[SIZE];   int find(int target) {     if (target == parent[target]) return target;     else return parent[target] = find(parent[target]); }   void Union(int a, int b) {     a = find(a);     b = find(b);     if (a != b) parent[b] = a; }   int N, M, sum;   int main() {     ios::sync_with_stdio(0), cin.tie(0);     cin >> N >> M;     for (int i = 1; i <= N; i++) parent[i] = i;     for (int i = 0; i < M; i++) {         cin >> V[i].s >> V[i].e >> V[i].value;     }     sort(V, V + M, cmp);          for (int i = 0; i < M; i++) {         int a = V[i].s, b = V[i].e;         if (find(parent[a]) != find(parent[b])) {             Union(a, b);             sum += V[i].value;         }     }     cout << sum;     return 0; } Colored by Color Scripter

cs