[백준 6497번] 전력난

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

전력난 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1306	468	327	32.766%

문제

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1 

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

최소 스패닝 트리 문제이다. 문제 분류에는 강한 연결 요소가 들어있어서 어려운 문제인줄 알았는데 크루스칼 알고리즘을 사용해서 스패닝 트리를 구하면 해결되는 간단한 문제였다.

#include<iostream>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int m,n,x,y,z,cnt;
int parent[200001],rank_cnt[200001];
long long value;
priority_queue<pair<int,pair<int,int>>> indegrees;
 
int find(int u){
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}
 
bool union_(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return false;
    if(rank_cnt[u] > rank_cnt[v]) swap(u,v);
    parent[u] = v;
    if(rank_cnt[u] == rank_cnt[v]) rank_cnt[v]++;
    return true;
}
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while(1){
        cin >> m >> n;
 
        value = 0;
        cnt = 0;
 
        while(!indegrees.empty()) indegrees.pop();
 
        if(m == 0 && n == 0) break;
 
        for(int i=0;i<n;i++){
            cin >> x >> y >> z;
            indegrees.push({-z,{x,y}});
            value += z;
        }
 
        for(int i=0;i<m;i++){
            parent[i] = i;
            rank_cnt[i] = 0;
        }
 
        while(!indegrees.empty() && cnt != m){
            x = indegrees.top().second.first;
            y = indegrees.top().second.second;
            z = -indegrees.top().first;
            indegrees.pop();
 
            if(union_(x,y)){
                cnt++;
                value -= z;
            }
        }
 
        cout << value << "\n";
    }
 
    return 0;
}