전력난

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int M,N;
int parent[200002]; // 1~200000 사용
// findParent()
int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}
// unionParent()
void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if(a<b) parent[b] = a;
    else parent[a] = b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while(true)
    {
        int ans=0; int tot=0;
        cin >> M >> N;
        if(M == 0 and N == 0) break;
        vector<pair<int, pair<int,int>>> edges;
        for(int i=0;i<N;i++)
        {
            int a, b, cost;
            cin >> a >> b >> cost;
            edges.push_back({cost,{a,b}});
            tot += cost;
        }
        // parent 초기화
        fill(parent, parent+200002, 0);
        for(int i=1;i<=M;i++) parent[i]=i;

        // edges 정렬
        sort(edges.begin(), edges.end());

        for(int i=0;i<edges.size();i++)
        {
            int a = edges[i].second.first;
            int b = edges[i].second.second;
            int cost = edges[i].first;
            if(findParent(a) != findParent(b)){
                unionParent(a,b);
                ans += cost;
            }
        }
        cout << tot - ans << '\n';
    }
}

• 핵심 아이디어
  • Kruskal 알고리즘 사용
  • 전체 cost를 더한 tot에서 MST에 포함하는 cost인 ans를 빼면 된다