POJ-1655: Balancing Act

keyword

グラフ　木　C++

問題概要

ノード数N(<20000)の木が与えられる。各ノードvに対してbalance(v)を、G-{v}の連結成分のもっとも大きい値と定義する。balance(v)を最小にするノードvとその値を求める問題。

解法

葉から順次処理していく。処理した葉はグラフから取り除き、新たに生じた葉をキューに突っ込んでいけばよい。計算量O(N)。
枝をkeyにしてメモ化再帰でといても良さげ。

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 20009;

vector<int> G[MAX_N];
int balance[MAX_N];
int childs[MAX_N];
int degs[MAX_N];
bool visited[MAX_N];
int N;

void subsolve(){
	queue<int> Q;
	for(int i=0; i<N; i++)if(degs[i]==1){
		Q.push(i);
	}
	while(!Q.empty()){
		int tp = Q.front(); Q.pop();
		visited[tp] = true;
		vector<int>& es = G[tp];
		int ma = 0, sum = 1;
		for(int i=0; i<(int)es.size(); i++){
			int u = es[i];
			if(visited[u]){
				ma = max(ma, childs[u]);
				sum += childs[u];
			}
			else if(--degs[u]==1){
				Q.push(u);
			}
		}
		balance[tp] = max(ma,N-sum);
		childs[tp] = sum;
	}
}

void solve(){
	int key = -1, best = 1<<20;
	subsolve();
	for(int i=0; i<N; i++){
		if(best > balance[i]){
			best = balance[i];
			key = i;
		}
	}
	printf("%d %d\n", key+1,best);
}

int main(){
	int T;
	for(scanf("%d",&T);T--;){
		scanf("%d",&N);
		memset(degs,0,sizeof(degs));
		memset(balance, 0, sizeof(balance));
		memset(childs, 0, sizeof(childs));
		memset(visited, 0, sizeof(visited));
		for(int i=0; i<N; i++){
			G[i].clear();
		}
		for(int i=0; i<N-1; i++){
			int x, y;
			scanf("%d%d",&x,&y);
			x--; y--;
			G[x].push_back(y); G[y].push_back(x);
			degs[x]++; degs[y]++;
		}
		solve();
	}
	return 0;
}