[백준]헤븐스 키친(14574)

문제 링크 : [백준]헤븐스 키친(14574)

14574번: 헤븐스 키친

 

문제 설명

N명의 참가자가 있고, 서로 경쟁을 하면서 이긴 사람을 떠나고, 패한 사람이 계속 경쟁을 이어갑니다.

N-1번의 게임을 이어가면서 시청률의 합을 최대로 하기 위하여 승자와 패자를 어떻게 결정해야 하는지, 그 때의 시청률이 몇인지 출력하세요.

입력

N(참가자 수, 1 <= N <= 1,000)

P_i(요리사의 실력, 0 <= P_i <= 1,000,000,000)

C_i(요리사의 인기도, 0 <= C_i <= 1,000,000,000)

3
1 2
3 1
5 3

 

출력

3
2 1
3 2

 

카테고리

#DFS #MST #크루스칼

 

시간 복잡도 상한

O(N²logN²)

 

해결 방법

1. 토너먼트를 생각하면 접근이 조금 쉽습니다.
2. 특이한 점은 진 사람이 계속 게임을 이어나가는데, 결국은 일반적인 토너먼트와 유사한 모양이 될 것입니다.
3. 그리고 토너먼트는 트리로 구성이됩니다.
4. 1명이 남을 때 까지 경쟁이 이어지기 때문에, N-1번의 경쟁이 이루어지고, 한 번 이긴 사람은 떠나기 때문에 싸이클이 발생할 수도 없습니다.
5. 결국 트리 모양인 것입니다.
6. 그 중에 트리를 구성하는 간선을 시청률로 보게 되면 최대 스패닝 트리로 시청률 합의 최대값을 구할 수 있습니다.
7. 그리고 MST를 구하면서 선택 된 간선들을 가지고 인접리스트를 구성합니다.
8. 이긴 사람이 떠나는 구조이기 때문에, DFS로 리프 노드까지 방문하고, 리프 노드가 승자, 부모가 패자가 되면, 문제에서 요구하는 답을 구할 수 있습니다.

시간복잡도

O(N²logN²)

코드

#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1001
#define F second.first
#define S second.second
using namespace std;
typedef pair<int,pair<int,int>>P;
int n,d[N][2],i,j,g[N];
long long s;
vector<P>v;
vector<int>w[N];
int f(int x){return x==g[x]?x:g[x]=f(g[x]);}
void u(int x,int y){g[f(x)]=f(y);}
void r(int p,int u){
    for(int x:w[p])if(x!=u)r(x,p);
    if(u)printf("%d %d\n",u,p);
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)g[i]=i,scanf("%d%d",d[i],d[i]+1);
    for(i=1;i<n;i++)for(j=i+1;j<=n;j++)v.push_back({(d[i][1]+d[j][1])/abs(d[i][0]-d[j][0]),{i,j}});
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(P x:v){
        if(f(x.F)!=f(x.S)){
            s+=x.first;
            w[x.F].push_back(x.S);
            w[x.S].push_back(x.F);
            u(x.F,x.S);
        }
    }
    printf("%lld\n",s);
    r(1,0);
}