BOJ)14950 정복자

문제:icpc.me/14950

모든 도시를 점거하는데 필요한 최소 비용을 출력하는 문제이다.

단 도시를 점거 해 나갈 때 마다 일정 비용이 추가 되었는 데 이것에 포커스를 맞추면 문제가 어려워 질 수 있다.

조금 생각을 해보면 결국 모든 도시를 점거해야하기 때문에 MST를 만들어주면 비용을 커버할 수 있는 걸 알 수 있다.

이미 MST를 구상하였다면 이에 이용 된 간선은 n-1개로 고정일 것이고, 이는 모든 도시를 점거하는데 필요한 간선의 최소 개수이기도 하기 때문에

(1~n-1 까지의 합) x t가 증가하는 비용으로 고정된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,k,par[10010];
vector<pair<int,pair<int,int>>> vt;
int find(int h){
    return h==par[h]?h:par[h]=find(par[h]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    par[x]=y;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        par[i]=i;
    for(int i=0;i<m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        vt.push_back({z,{x,y}});
    }
    sort(vt.begin(),vt.end());
    int it=n-1;
    long long res=0;
    for(auto next:vt){
        if(!it)break;
        if(find(next.second.first)==find(next.second.second))continue;
        merge(next.second.first,next.second.second);
        it--;
        res+=next.first;
    }
    long long v=((n-2)*(n-1))/2;
    res+=v*k;
    printf("%lld\n",res);
    return 0;
}