JOI春合宿 2010-day2 Regions

問題文 : 地域

解法 :
C(x) : 距離x以下でM個の地域に分割できるか、とすると
C(x)が成立すればC(x - 1)も成立するので、xについて二分探索を行う.
実際に距離xを超えるかは, 与えられたグラフを根付き木にし, 2つの辺によって結ばれる地域のコストの和を距離とし、それで判定する.
コストがxを超えればMから1を引き、最後まで処理をした結果Mが非負整数であればC(x)が真であることが分かる.
このコードは, 上記のことを実装しており, O(NlogN)時間で動作する.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N (30000)

typedef struct {
	int to;
	int cost;
} Edge;

typedef struct {
	vector<int> ch;
	vector<int> cost;
} Node;

vector<Edge> G[MAX_N];
Node T[MAX_N];
bool vis[MAX_N];

int lim;
int center;

void initTree(int v)
{
	vis[v] = true;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i].to]){
			T[v].ch.push_back(G[v][i].to);
			T[v].cost.push_back(G[v][i].cost);
			initTree(G[v][i].to);
		}
	}
}

int makeRegion(int v)
{
	int sz = (int)T[v].ch.size();
	int *S = (int *)malloc(sizeof(int) * (sz + 2));
	for (int i = 0; i < sz; i++){
		S[i] = makeRegion(T[v].ch[i]) + T[v].cost[i];
	}
	S[sz] = 0;
	S[sz + 1] = 0;
	
	sort(S, S + sz + 2);
	
	int pos = sz + 2;
	while (S[pos - 1] + S[pos - 2] > center){
		pos--;
		lim--;
	}
	int ret = S[pos - 1];
	free(S);
	
	return (ret);
}

int main()
{
	int N, M;
	int sum;
	
	scanf("%d %d", &N, &M);
	
	sum = 0;
	for (int i = 0; i < N - 1; i++){
		int a, b, c;
		Edge e;
		scanf("%d %d %d", &a, &b, &c);
		sum += c;
		e.to = --a; e.cost = c;
		G[--b].push_back(e);
		e.to = b;
		G[a].push_back(e);
	}
	
	initTree(0);
	int left = 0, right = sum;
	
	while (left != right){
		center = (left + right) / 2;
		lim = M - 1;
		makeRegion(0);
		
		if (lim < 0){
			left = center + 1;
		}
		else {
			right = center;
		}
	}
	
	printf("%d\n", left);
	
	return (0);
}