[BOJ 13209] 검역소

https://www.acmicpc.net/problem/13209

13209번: 검역소

 

- 문제 요약

 

한 나라에는 N 개의 도시들이 있고, 두 도시 사이를 연결하는 길이 N − 1개 있다.

어느 두 도시도 오직 하나의 경로로만 서로 통행할 수 있게 되어 있고, 이곳에는 몇 년에 한 번씩 큰 전염병이 돈다.

정부에서는 이 문제를 해결하기 위해 N −1 개의 길들 중 K 개의 길에 검역소를 운영하려고 한다.

또한, 어떤 사람이 전염병에 감염될 경우를 대비하여 치료제를 비축해 두려고 한다.

어떤 한 사람이 전염병에 감염될 때에도 전염병에 걸릴 수 있는 모든 사람들이 치료제를 하나씩 받을 수 있게 하기 위해 비축해야 할 치료제의 최소 개수를 구하여라.

 

 

- 알고리즘 정리

 

필요한 치료제의 최소 개수를 구하는 문제입니다. 

이분 탐색을 하면서 dfs로 각 정점에서 탐색을 진행해줍니다. 

탐색을 하면서 각 컴포넌트 가중치의 합이 mid 값(이분탐색)보다 작아지도록 나눠주고, 제거한 간선의 개수가 K보다 작은지 확인해 주면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
int t,n,k;
ll arr[MAX],mx,cnt,l,r;
vector<int>v[MAX];

ll dfs(int x,int w=-1){
	priority_queue<ll>pq;
	ll now=arr[x];
	for(auto i:v[x]){
		if(i!=w){
			ll tmp=dfs(i,x);
			now+=tmp;
			pq.push(tmp);
		}
	}
	while(pq.size()&&now>mx){
		now-=pq.top();
		pq.pop();
		cnt++;
	}
	return now;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>t;
	while(t--){
		ll sum=0;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>arr[i];
			sum+=arr[i];
			v[i].clear();
		}
		for(int i=1;i<n;i++){
			ll s,e;
			cin>>s>>e;
			v[s].push_back(e);
			v[e].push_back(s);
		}
		ll l=*max_element(arr+1,arr+n+1);
		r=sum;
		while(l<r){
	        ll mid=(l+r)/2;
	        cnt=0;
	        mx=mid;
	        dfs(1);
	        if(cnt<=k){
	        	r=mid;
			}
			else{
				l=mid+1;
			}
		}
		cout<<r<<'\n';
	}
}

코드 제출 결과