도시 분할 계획 (feat. 백준, 1647번)

도시 분할 계획
https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[100001];
vector<pair<int, int>> arr[100001];
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 N, M;
    cin >> N >> M;
    memset(visit, false, N);
    for(register int m = 0, a, b, c; m < M; ++m){
        cin >> a >> b >> c;
        arr[a].push_back(make_pair(b, c)), arr[b].push_back(make_pair(a, c));
    }
    q.push(make_pair(0, 1));
    register int next, nnext, cost, max_value = 0, total = 0;
    while(!q.empty()){
        next = q.top().second, cost = q.top().first; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        total += cost;
        if(cost > max_value)
            max_value = cost;
        for(auto& v : arr[next]){
            nnext = v.first;
            if(visit[nnext])
                continue;
            cost = v.second;
            q.push(make_pair(cost, nnext));
        }
    }
    cout << total - max_value;
	return 0;
}
// *&)*@*

 

반응형

문제 자체가 이해가 안가서 한참 고민했습니다.

결국 N-1개의 집이 있는 마을과 1개의 집이 있는 마을로 기준을 잡고 하나의 길을 없앴을때의 최소 유지비를 구하는 문제입니다.

따라서 전체 유지비에서 최대 유지비를 빼면 정답이 되겠습니다.