[PS] 백준 1647번: 도시 분할 계획

|

문제

내가 이해한 문제 내용

마을의 길 유지비 합을 최소로 하면서 2개의 마을로 분할하시오.

접근 방식

MST 구하고 간선 가중치의 최댓값을 빼준다. 아예 안보고 구현하다보니 정렬이 아니라 우선순위 큐를 썼다.

어려웠던 점 & 배운 점

우선순위 큐에서 오름차순은 greater를 사용해야 하는데 연산자 오버로딩을 할 때 >를 오버로딩 해야 한다.

시간복잡도

우선순위큐의 시간복잡도가 $O(ElgE)$이고 유니온-파인드가 $O(\alpha(E))$이므로 $O(ElgE+\alpha(E))$인데 스패팅 트리에서 간선의 개수는 $V-1\le E \le V^2$를 만족하므로 $O(ElgE)=O(ElgV^2)=O(2ElgV)=O(ElgV)$이다. 여기서 $E \le V^2$인 이유는 질문했던 것을 참고하자.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

struct edge{
    int v1;
    int v2;
    int weight;

    bool operator>(const edge& e) const{
        return weight>e.weight;
    }
};

priority_queue<edge,vector<edge>,greater<edge> > pq;
int n,m,a,b,c,ans;
int p[100001],r[100001];

int find(int v){
    if(p[v]==v) return v;
    else return p[v] = find(p[v]);
}

void uni(int v1, int v2){
    int p1 = find(v1);
    int p2 = find(v2);

    if(r[p1]<r[p2]) p[p1] = p2;
    else if(r[p1]>r[p2]) p[p2] = p1;
    else if(r[p1]==r[p2]){
        r[p1]++;
        p[p2] = p1;
    }
}

int main(void)
{
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        pq.push({a,b,c});
    }

    for(int i=1; i<=n; i++){
        p[i] = i;
        r[i] = 1;
    }

    int max = 0;
    while(!pq.empty()){
        edge e = pq.top(); pq.pop();
        int v1 = e.v1, v2 = e.v2;
        if(find(v1)!=find(v2)){
            ans += e.weight;
            if(max<e.weight) max = e.weight;
            uni(v1,v2);
        }
    }

    printf("%d",ans-max);

    return 0;
}