[백준]물대기(1368)

문제 링크 : [백준]물대기(1368)

1368번: 물대기

 

문제 설명

N개의 논에

1. 직접 우물을 파거나,
2. 이미 물을 대고 있는 논에서 물을 끌어옴

두 가지 작업을 통하여 모든 논에 물을 대고자 합니다.

두 가지에 대한 비용이 주어졌을 때, 모든 논에 물을 대는 최소 비용을 구하세요.

입력

N(논의 갯수, 1 <= N <= 300)

W_i(i번째 논에 우물을 파는 비용, 1 <= W_i <= 100,000)

P_ij(i번째 논에서 j번째 논을 잇는데 필요한 비용, <= P_ij <= 100,000)

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

 

출력

9

 

카테고리

#MST #크루스칼

 

시간 복잡도 상한

O(N³)

 

해결 방법

1. 각 논에 대해서 우물을 파거나, 다른 우물과 잇는 작업 중 하나의 작업이 이루어져야 합니다.
2. 완성된 그래프의 모양을 생각해보면, 하나 이상의 우물은 반드시 존재해야 하며, 그 우물을 중심으로 트리가 형성이 될 것입니다.
   1. K개의 우물이 연결 되었는데, 싸이클이 존재한다면 모두 다른 논에 이어져 있는 모양이므로, 내부에 우물을 판 논이 없는 경우라서 절대로 존재 할 수 없는 경우입니다.
3. 즉, 트리인데 트리를 만드는 최소 비용을 구하는 문제, MST문제로 볼 수 있습니다.
4. 다만, 트리가 한 개 이상으로 구성이 될 수 있습니다.
5. 이 때, 직접 우물을 파는 경우를 0번 노드(가상의 노드)에 연결하는 간선으로 만들고, 비용은 직접 우물을 파는 비용으로 MST를 구하면 답을 구할 수 있습니다.

시간복잡도

O(N²logN²)

코드

#include<cstdio>
#include<vector>
#include<algorithm>
#define F first
#define S second
using namespace std;
typedef pair<int,pair<int,int>>P;
int n,t,m,i,j,s,g[301];
vector<P>v;
int f(int a){return a==g[a]?a:g[a]=f(g[a]);}
void u(int a,int b){
    g[f(a)]=f(b);
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&t),v.push_back({t,{i,0}}),g[i]=i;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&t);
            if(i<j)v.push_back({t,{i,j}});
        }
    }
    sort(v.begin(),v.end());
    for(P p:v){
        i=p.S.F;j=p.S.S;
        if(f(i)!=f(j))s+=p.F,u(i,j);
    }
    printf("%d",s);
}