[백준] 14574 헤븐스 키친

이 프로그램에 출연하는 N명의 요리사는 각각 요리 실력 Pi와 인기도 Ci를 갖고 있다.

이 프로그램의 시청률은 그 날 요리 대결을 펼치는 두 요리사의 요리 실력과 인기도에 의해 결정된다.

남규는 총 N-1번의 경기 동안, 경기 순서와 승패를 잘 정해서 시청률의 총합을 최대화 → N명의 요리사가 있으면 N-1번의 경기를 치루고, 각 경기마다 시청률이라는 값을 지니고 있으며 각 경기들의 시청률의 합을 최대화하는 방법을 구해야 한다. N명의 요리사를 노드로 두고 N-1번의 경기를 간선으로 생각한다면 이는 트리의 형태가 되고, 최소(최대) 스패닝 트리를 구하는 문제로 볼 수 있다.

 

→ 어떤 경기(i번째 요리사 vs. j번째 요리사)가 이루어져야 최대 시청률합이 나오는지 알 수 있다. 하지만 어떤 순서로 경기를 진행해야하는지는 알 수 없다.

 

4번 요리사까지 있고, 위와 같이 빨간 경기를 진행해야지 최대 시청률합이 나온다고 가정하자. 만약 1번 요리사부터 dfs를 거친다면 1 → 2 → 4 → 3 순서가 된다. 이때 dfs에서 자신의 부모노드의 값을 지닌다면 (0, 1) → (1, 2) → (1, 4) → (1, 3) 이 되고, 이는 경기에 투입되는 요리사 정보와 같아진다. 이때 표현된 부모노드가 요리사의 번호이고(0이 아니고), & 자신의 자식 노드를 다 탐색하여 없는 상태라면 경기를 치룰 수 있고 이를 출력하면 경기 순서와 같아진다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 1001
typedef long long ll;

int N, P, C, ap, bp;
ll sum = 0;
vector<pair<int, int>> PC(MAX_N);
vector<pair<int, pair<int, int>>> edges;
vector<int> new_edges[MAX_N];
int parent[MAX_N];


int find_parent(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find_parent(parent[a]);
}

void dfs(int cur, int target) {
    for (int nxt : new_edges[cur]) {
        if (nxt != target) dfs(nxt, cur);
    }
    if (target) cout << target << " " << cur << '\n'; 
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> P >> C;
        parent[i] = i;
        PC[i] = {P, C};
    }
    for (int i = 1; i < N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            edges.push_back({ (PC[i].second+PC[j].second)/abs(PC[i].first-PC[j].first) , {i, j} });
        }
    }

    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());
    for (pair<int, pair<int, int>> e : edges) {
        ap = find_parent(e.second.first);
        bp = find_parent(e.second.second);
        if (ap != bp) {
            sum += e.first;
            
            new_edges[e.second.first].push_back(e.second.second);
            new_edges[e.second.second].push_back(e.second.first);
            
            parent[ap] = bp;
        }
    }

    cout << sum << '\n';
    dfs(1, 0);

    return 0;
}