[백준]전기가 부족해(10423)

문제 링크 : [백준]전기가 부족해(10423)

10423번: 전기가 부족해

문제 설명

N개의 도시와 M개의 설치 가능한 케이블 정보가 주어집니다.

K개의 발전소 정보가 주어질 때, 모든 도시에 전기 공급이 가능하도록 케이블을 설치 할 때 최소 비용을 구하세요.

단, 모든 도시는 하나의 발전소와 연결되어 있어야합니다.(두 개 이상 불가능)

입력

N(도시의 갯수, 1 <= N <= 1,000)

M(케이블 갯수, 1 <= M <= 100,000)

K(발전소 갯수, 1 <= K <= N)

B_i(발전소가 세워진 도시 번호)

U_i V_i W_i(케이블 정보, U_i와 V_i 도시가 이어지며, W_i 비용이 발생함)

9 14 3
1 2 9
1 3 3
1 4 8
2 4 10
3 4 11
3 5 6
4 5 4
4 6 10
5 6 5
5 7 4
6 7 7
6 8 4
7 8 5
7 9 2
8 9 5

 

출력

22

 

카테고리

#MST #크루스칼

 

시간 복잡도 상한

O(N³)

 

해결 방법

1. 모든 도시가 직간접적으로 발전소에 연결이 되어야하며, 그 비용이 최소여야 합니다.
2. MST를 구하는 문제와 동일합니다.
3. 단, 모든 마을은 발전소 하나만 연결되어야 합니다.
4. 하나의 발전소와 연결된 마을이 다른 발전소와 연결된 마을과 연결 되는 것을 막으면 됩니다.
5. 즉, 위와 같은 경우에 싸이클이 발생한 것으로 간주하면 처리가 편해 질 것 같습니다.
6. 크루스칼을 시작하기 전, 모든 발전소가 설치된 마을을 모두 Union 처리하여 하나의 그룹으로 묶은 후, 크루스칼을 수행하면 답을 구할 수 있습니다.

시간복잡도

O(MlogM)

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    int a,b,c;
    bool operator<(const P&x)const{
        return c<x.c;
    }
}v[100000];
int n,m,k,g[1001],i;
long long x;
int f(int x){
    return g[x]==x?x:g[x]=f(g[x]);
}
void u(int a,int b){
    g[f(a)]=f(b);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)g[i]=i;
    for(i=0;i<k;i++)cin>>x,u(0,x);
    for(i=0;i<m;i++)cin>>v[i].a>>v[i].b>>v[i].c;
    sort(v,v+m);
    for(i=x=0;i<m;i++){
        if(f(v[i].a)!=f(v[i].b))x+=v[i].c,u(v[i].a,v[i].b);
    }
    cout<<x;
}