백준 01647 - 도시 분할 계획

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

1647번: 도시 분할 계획

 

고려사항

• 최소 신장 트리 문제!
• 도시를 두 개로 분할했을 때의 최소 도로 비용은
  최소 신장 트리로 모든 도시를 연결했을 때, 가장 비싼 비용의 도로를 제거해주면 2개로 나뉜다!
• 프림 방식으로 풀었다.
• 프림 방식은
  1. 노드(vertex)를 선택 하고, 그 노드에 연결된 edge들을 minHeap 에 담아준다.
  2. 힙에서 e를 꺼내고, 해당 e를 통해 연결되는 지점이 미방문 상태라면 트리에 포함시킨다.
  3. 새로운 지점을 기준으로 다시 1번 과정을 반복한다.
  4. 결과적으로 모든 지점을 방문하게 되었을 때, 선택된 노드와 엣지들이 최소 신장 트리이다.
• 크루스칼 방식은
  1. edge들을 전부 minHeap 에 담아준다.
  2. 제일 작은 가중치를 지닌 엣지를 꺼내어 트리에 포함시킨다.
  3. 이 때, edge의 두 지점을 같은 그룹에 포함 시킨다. ( Union - Find 사용! )
  4. 만약 3번 과정에서 이미 둘이 같은 지점이라면, 포함시키지 않고 skip 한다.
  5. 노드의 수가 n 일 때, n-1개의 엣지들을 선택했을 때 까지 2번부터 반복한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, m, maxW = -1;
vector<pair<int, int>> v[100001];
bool visit[100001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
int main(){
    cin>>n>>m;
    int a, b, c;
 
    for(int i=0;i<m;++i){
        cin>>a>>b>>c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }
 
    visit[1] = true;
    for(pair<int, int> e : v[1]){
        pq.push(e);
    }
 
    int next, w, sum = 0;
    while(!pq.empty()){
        w = pq.top().first;
        next = pq.top().second;
        pq.pop();
 
        if(visit[next]){
            continue;
        }
 
        sum += w;
        maxW = max(w, maxW);
        visit[next] = true;
 
        for(pair<int, int> p : v[next]){
            if(!visit[p.second]){
                pq.push(p);
            }
        }
    }
 
    cout<<sum - maxW;
    return 0;
}