[백준][C++] 6497 전력난

6497. 전력난
문제 풀이

6497번: 전력난

 

기본적인 MST 문제였다. 전체 비용 - MST의 비용이 절약할 수 있는 최대 비용이기 때문이다.

알고리즘 설계

1. 간선을 입력받으며 간선들과 간선들의 모든 가중치를 더해 저장한다.
2. 간선들을 가중치 기준으로 오름차순 정렬한다.
3. union-find와 memoization을 사용해 사이클이 생기지 않게 크루스칼 알고리즘을 이용해 MST의 비용을 구한다.
4. 모든 간선의 가중치의 합 - MST 비용을 출력한다.

코드

#include<bits/stdc++.h>
using namespace std;

struct Edge
{
    int a, b, w;

    bool operator < (const Edge& e) const
    {
        return w < e.w;
    }
};

int parent[200001];

// union-find + memoization
int find(int v)
{
    vector<int> children;

    while (parent[v] != v)
    {
        v = parent[v];
        children.push_back(v);
    }

    for (int i : children)
    {
        parent[i] = v;
    }

    return v;
}

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    // testCase
    while (true)
    {
        int vCnt, lCnt;
        long long int total = 0, result = 0;
        vector<Edge> edges;

        cin >> vCnt >> lCnt;

        for (int i = 0; i <= vCnt; i++)
        {
            parent[i] = i;
        }

        // kruskal
        for (int i = 0; i < lCnt; i++)
        {
            int a, b, w;
            cin >> a >> b >> w;

            edges.push_back({ a,b,w });
            total += w;
        }

        sort(edges.begin(), edges.end());

        for (int i = 0; i < edges.size(); i++)
        {
            int fa = find(edges[i].a);
            int fb = find(edges[i].b);

            if (fa != fb)
            {
                parent[fa] = fb;
                result += edges[i].w;
            }
        }

        // max - min
        cout << total - result << '\n';
    }
}

유익한 문제였다 ^__^!!