백준 21924 도시건설

algorithm : 최소비용신장트리, union_find

 

해설

 

우선순위큐를 사용하여 간선이 작은 순으로 나오게 한다 우선순위큐의 top의 a,b가 다른 그룹일 경우는 둘을 잇는다

만약 큐를 다 돌고 나서 모든 노드들은 1개의 그룹이여야 한다. 만약 1개의 그룹이지 않으면 모든 노드가 연결되어 있지 않기 때문에 -1을 출력한다

예를 보았을때 이런 순서로 간선이 연결된다

#include<bits/stdc++.h>
#define LM 500000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N,M;
int A,B,C;
int Union[LM];
LL ans,sum;
int visit[LM];
struct data{
    int a,b,c;
    bool operator<(const data &r)const{
        return r.c < c;
    }
};
priority_queue<data> pq;

void input(){
    scanf("%d %d",&N,&M);
    for(int i = 1 ; i <= M ; i++){
        scanf("%d %d %d",&A,&B,&C);
        pq.push({A,B,C});
        sum += C;
    }
}

int getparent(int pos){
    if(pos == Union[pos]) return pos;
    else return Union[pos] = getparent(Union[pos]);
}

void Kruskal(){
    for(int i = 1 ; i <= N ; i++) Union[i] = i;
    while(!pq.empty()){
        auto t = pq.top();
        pq.pop();
        A = getparent(t.a);
        B = getparent(t.b);
        if(A == B) continue;
        visit[t.a] = visit[t.b] = 1;
        Union[B] = A;
        ans += t.c;
    }
    A = getparent(1);
    for(int i = 2 ; i <= N ; i++){
        if(A != getparent(i)){
            printf("-1");
            return;
        }
    }
    printf("%lld",sum - ans);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    Kruskal();
    return 0;
}