전력난 (feat. 백준, 6497번)

전력난
https://www.acmicpc.net/problem/6497

6497번: 전력난

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int, int>> arr[200000];     // 다음 집, 거리
bool visit[200000];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;       // 거리, 다음 집
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int m, n;
    while(true){
        cin >> m >> n;
        if(m == 0)
            break;
        if(n == 0){
            cout << 0 << '\n';      // 켜진 길이 없으므로 끌 수 있는 길도 없음
            continue;
        }
        for(register int i = 0; i < m; ++i)
            arr[i].clear(), visit[i] = false;
        register long long ans = 0, total = 0;
        register int next, nnext, dist;
        for(register int i = 0, x, y, z; i < n; ++i)
            cin >> x >> y >> z, total += z, arr[x].push_back(make_pair(y, z)), arr[y].push_back(make_pair(x, z));
        q.push(make_pair(0, 1));
        while(!q.empty()){
            dist = q.top().first, next = q.top().second; q.pop();
            if(visit[next])
                continue;
            visit[next] = true;
            ans += dist;
            for(auto& v : arr[next]){
                nnext = v.first, dist = v.second;
                if(!visit[nnext])
                    q.push(make_pair(dist, nnext));
            }
        }
        while(!q.empty())           // queue 초기화
            q.pop();
        cout << total - ans << '\n';            // 전체 켜진 길의 값 - MST의 해
    }
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 프림 알고리즘을 사용하여 풀이하였습니다.

 

하나의 문제에 여러가지 테스트 케이스가 오는 경우, 기존 변수들의 초기화에 신경써야 합니다.

또한 해당 문제는 켜진 길 (MST로 구해진 값) 을 출력하는 것이 아니라 최대로 끌 수 있는 길 (전체 - MST로 구해진 값) 을 출력하는 문제입니다.