1197

반성해야하는 문제다

너무 문제에 성급하게 접근했다.

최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다.

나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다.

이것은 union find라는 자료구조를 이용해서 해결해야하는데

나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다.

(아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..)

프림알고리즘을 사용했으면 틀리지 않았을 것 같다...

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int height[100001]; int par[100001]; struct Node{ int con_a, con_b; int weight; }; bool compare(Node a, Node b){ return a.weight < b.weight; } bool found[100001]; Node edges[100001]; void init(int n){ for(int i = 1; i <= n; i++){ par[i] = i; height[i] = 0; } } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } void unite(int a, int b){ a = find(a); b = find(b); if(a == b) return; if(height[a]<height[b]){ par[a] = b; }else{ par[b] = a; if(height[a]==height[b]) height[a]++; } } int main() { int V, E; long long sum = 0; scanf("%d %d", &V, &E); for(int i=1; i<=V; i++) found[i]=false; init(V); for(int i=0; i<E; i++) { scanf("%d %d %d", &edges[i].con_a, &edges[i].con_b, &edges[i].weight); } sort(&edges[0], &edges[E], compare); for(int i=0; i<E; i++) { if(find(edges[i].con_a) == find(edges[i].con_b)){ } else{ sum += edges[i].weight; unite(edges[i].con_a, edges[i].con_b); } } printf("%lld\n", sum); return 0; }