[6497번] Dark roads

문제 출처 :

https://www.acmicpc.net/problem/6497

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

2. 유니온 파인드(Union Find) :: http://www.crocus.co.kr/683

이 문제의 해석은 다음과 같다.

어떤 도시가 있는데 그 도시에 돈이 이제 부족하여 가로등을 다 꺼야하는 상황에 왔다.

하지만 최소로 불을 켜 두자고 결정이 났고, 결국 교차점마다 하나의 불을 무조건 켜져있도록 하자고 하였다.

결국 이 빨간 간선들이 최소 스패닝 트리를 의미하고 있고, 

정답은 정부가 아낄 수 있는 최대 금액이니 전체 간선 - 최소 스패닝 트리 간선 길이를 의미한다.

소스 코드 : 

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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cmath>   using namespace std;   typedef struct kruskal {     int from;     int to;     int val; }KS;     int parent[200002]; int res; int sum;     bool comp(KS d1, KS d2) {     return d1.val < d2.val; }   // 유니온 파인드의 파인드 방식 int find(int num) {     if (num == parent[num])         return num;       return parent[num] = find(parent[num]); } int main() {     int V, E;       while(1)     {         scanf("%d %d", &V, &E);           if (V == 0 && E == 0)             break;           // 초기화         for (int i = 0; i <= V; i++)             parent[i] = i;           vector<KS> edge;           sum = 0;         res = 0;           // 그래프 형성         for (int i = 0; i < E; i++)         {             KS ks;             scanf("%d %d %d", &ks.from, &ks.to, &ks.val);             edge.push_back(ks);             sum += ks.val;         }           // 크루스칼 알고리즘에 의해 간선을 오름차순 정렬         sort(edge.begin(), edge.end(), comp);           // 유니온 파인드의 유니온 방식         for (int i = 0; i < E; i++)         {             int nv = find(edge[i].from);             int nw = find(edge[i].to);               if (nv == nw)                 continue;               parent[nv] = nw;               res += edge[i].val;         }           printf("%d\n", sum - res);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus