[백준] 6497번 : 전력난 (C++)

6497번 : 전력난

---

문제)

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

 

 

입력 :

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

 

 

 

출력 :

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

 

 

 

 

 

풀이)

모든 집이 연결되었을 때 최소 값을 찾아야하는 문제이므로

최소 스패닝 트리 문제임을 판단했다.

 

들어오는 입력값들을 가중치 기준으로 정렬한 다음.

가중치가 작은 값부터 차근차근 연결해주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
 
vector<int> par;
vector<vector<int>> vec;
 
int _find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else return par[x] = _find(par[x]);
}
 
 
void _union(int x, int y)
{
    int a = _find(x);
    int b = _find(y);
    
    if (a == b) return;
    par[a] = b;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    while (true)
    {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        
        par.clear();
        for (int i = 0; i < n + 1; i++) par.push_back(i);
        vec.clear();
 
        int total = 0;
        int a, b, c;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b >> c;
            vec.push_back(vector<int> { a, b, c });
            total += c;
        }
        
        sort(vec.begin(), vec.end()
            , [](vector<int> a, vector<int> b)
                { return a[2] < b[2]; });
    
        int ans = 0;
        for (int i = 0; i < m; i++)
        {
            a = vec[i][0];
            b = vec[i][1];
            if (_find(a) == _find(b)) continue;
 
            _union(a, b);
            ans += vec[i][2];
        }
 
        cout << total - ans << "\n";
    }
 
    return 0;
}

---

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

6497번: 전력난