[백준 6497번] 전력난

문제 링크: https://www.acmicpc.net/problem/6497

6497번: 전력난

<문제 풀이> 최소 스패닝 트리, 크루스칼 알고리즘

 

크루스칼 알고리즘으로 최소 비용으로 모든 집을 연결하고, 연결된 비용의 총합을 전체 간선의 비용 총합에서 빼주면 됩니다.

 

<C++소스코드>

 

#include<iostream>
#include<vector>
#include<utility>
#include<tuple>
#include<algorithm>
using namespace std;

const int MAX_N = 200000;
vector<tuple<int, int, int> > edge;
int parents[MAX_N];

int Find(int x) {
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

void Union(int x, int y) {
    int x_parents = Find(x);
    int y_parents = Find(y);
    if (x_parents < y_parents) parents[x_parents] = y_parents;
    else parents[y_parents] = x_parents;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
  
    while (true) {
        int n, m; cin >> n >> m;
        if (n == 0 && m == 0) break;
        edge = {};
        for (int i = 0; i < n; i++) parents[i] = i;

        int tot = 0;
        for (int i = 0; i < m; i++) {
            int u, v, w; cin >> u >> v >> w;
            edge.push_back({ w, u, v });
            tot += w;
        }

        sort(edge.begin(), edge.end());
        int cnt = 0, res = 0;
        for (auto& e : edge) {
            int w, u, v; tie(w, u, v) = e;
            if (Find(u) == Find(v)) continue;
            Union(u, v);
            cnt++;
            res += w;
            if (cnt == n - 1) break;
        }
        cout << tot - res<<'\n';
    }

    return 0;
}