BOJ 13209 - 검역소

문제 링크 : https://www.acmicpc.net/problem/13209

문제 태그

Parametric Search

문제 소개

트리가 있다. 이중 k개의 간선을 끊어서 k+1개의 트리로 만든다. 이때 각 트리에 포함된 노드의 가중치의 합들 중 최댓값의 최솟값을 구하시오. 

문제 풀이

트리의 간선을 '최대한 잘' 끊어야 한다. 트리별로 노드의 가중치의 합이 최대한 비슷하도록, 어느한쪽이 치우치지 않도록 끊어야 한다. 어떻게 해야 최대한 잘 끊을 수 있을까?

이를 생각하는 문제는 굉장히 어렵다. 너무 다양한 경우의 수가 나오게 된다. 따라서 좀 다른 방식을 생각해보자. 트리에서 어떻게 잘 잘라서 "가능한 최솟값"을 물어보는 문제이다. x가 된다면 당연히 x이상은 모두 다 가능하고, x가 불가능하면 x이하로는 모두 불가능하다. 그렇다. "파라메트릭 서치"를 한 번쯤 의심해봐야한다. 

값의 최솟값이 되도록 간선을 잘 끊는 것은 굉장히 어려운 문제이다. 하지만 값이 x이하가 되도록 끊는 것은, 그냥 더해나가면서 x를 넘을 때마다 끊어주면된다. 즉 트리에서 탐색을 하면서 그리디하게 해줄 수 있다는 것이다. 그리디가 가능해졌으므로 끊는 것을 결정하는 문제가 굉장히 쉬워졌고, k개 이하만 사용해서 트리 전체를 x이하의 가중치들로 분리할 수 있는지 확인만 하면 된다. 어떤 x에 대해서 결정하는 데 시간복잡도가 $O(N)$이므로 대략 전체 시간복잡도 $O(NlgN)$에 문제를 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define maxn 101010
 
ll vis[maxn];
ll peo[maxn];
ll n,k,t,block;
ll vacc;
vector<ll> con[maxn];
 
ll dfs(int idx) {
    ll val,sum = 0;
    priority_queue<ll> pq;
    vis[idx]=1;
 
    for (auto ver : con[idx])
    {
        if(vis[ver]==1) continue;
        val=dfs(ver);
        sum+=val;
        pq.push(val);
    }
 
    while (!pq.empty()&&sum+peo[idx]>vacc)
    {
        block++;
        sum-=pq.top();
        pq.pop();
    }
    return sum+peo[idx];
}
 
int main()
{
    ll i,j,k,a,b;
    scanf("%lld", &t);
    while (t--)
    {
        ll lo=0,ans=0,hi=0,mid;
        scanf("%lld %lld",&n,&k);
        for (i=1;i<=n;i++)
        {
            scanf("%lld",&peo[i]);
            lo=max(lo,peo[i]);
            hi+=peo[i];
            con[i].clear();
        }
        for (i=1;i<n;i++)
        {
            scanf("%lld %lld",&a,&b);
            con[a].push_back(b);
            con[b].push_back(a);
        }
        while (lo<=hi)
        {
            mid=(lo+hi)/2;
            block=0;
            vacc=mid;
            for(i=1;i<=n;i++) vis[i]=0;
            dfs(1);
            if (block<=k)
            {
                hi=mid-1;
                ans=mid;
            }
            else lo=mid+1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}