[Algorithm]Baekjoon 6497번 :: 전력난

https://www.acmicpc.net/problem/6497

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
 
struct Node
{
    int x, y, z;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.z < b.z;
}
 
int m, n, x, y, z;
int parents[2000001] = { 0 };
 
 
int GetParents(int node)
{
    if (node == parents[node])
    {
        return node;
    }
 
    return parents[node] = GetParents(parents[node]);
}
 
void UnionParents(int node1, int node2)
{
    int node1Parent = GetParents(node1);
    int node2Parent = GetParents(node2);
 
    if (node1Parent < node2Parent)
    {
        parents[node2Parent] = node1Parent;
    }
    else
    {
        parents[node1Parent] = node2Parent;
    }
}
 
bool IsSameParents(int node1, int node2)
{
    return GetParents(node1) == GetParents(node2);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    vector<int> answers;
   
    while (1)
    {
        cin >> m >> n;
 
        if (m == 0 && n == 0)
        {
            break;
        }
 
        int sum = 0;
        vector<Node> nodes(n);
 
        for (int i = 0; i < m; ++i)
        {
            parents[i] = i;
        }
 
        for (int i = 0; i < n; ++i)
        {
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].z; 
        }
 
        sort(nodes.begin(), nodes.end(), cmp);
 
        for (int i = 0; i < n; ++i)
        {
            if (!IsSameParents(nodes[i].x, nodes[i].y))
            {
                UnionParents(nodes[i].x, nodes[i].y);
            }
            else
            {
                sum += nodes[i].z;
            }
        }
 
        answers.push_back(sum);
    }
   
    for (int i = 0; i < answers.size(); ++i)
    {
        cout << answers[i] << endl;
    }
 
    return 0;
}
 
 
 
 
 

 

무난한 MST문제이다. 알고리즘 오랜만에 풀어도 UnionParent로 하는 MST는 손에 익어서 그런가, 쉽게쉽게 작성된다.

 

그나마 한가지 유의할 점은, 문제에서의 답은 '아낀 돈'이다. MST를 만드는데 사용된 돈이 아니라, 아낀 돈이니까 합칠때 말고 그냥 넘어갈 때 sum값에 누적시켜주면 된다.