도시 분할 계획

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N,M,ans,max_cost;
int parent[100002]; // 1~100000 사용
int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if(a<b) parent[b] = a;
    else parent[a] = b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    vector<pair<int, pair<int,int>>> edges;
    for(int i=0;i<M;i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        edges.push_back({cost,{a,b}});
    }
    // parent 초기화
    for(int i=1;i<=N;i++)
        parent[i] = i;

    // edges 정렬
    sort(edges.begin(), edges.end());

    for(int i=0;i<edges.size();i++)
    {
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        int cost = edges[i].first;
        if(findParent(a) != findParent(b)){
            unionParent(a,b);
            max_cost = max(max_cost, cost);
            ans += cost;
        }
    }
    cout << ans - max_cost;
    return 0;
}

• 핵심 아이디어
  • 두개의 마을로 나눌 때 어차피 하나의 간선을 끊어야 한다
  • 즉, 가장 cost가 큰 간선을 끊으면 최소값을 구할 수 있다

• Kruskal 알고리즘의 시간복잡도
  • O(ElogV) : E은 간선의 개수

• Prim 알고리즘의 시간복잡도
  • O(V^2) : V은 노드의 개수
  • priority queue로 구현 : O(ElogV)