予備役将校訓練部隊のピクニック

アルゴリズムデザインにのっていた問題。
本当は動的計画法を使うらしいけど、よく分からないので、BFSした。

問題
木が与えられる。この木の根から情報を発信する。情報は、時間１の間に各ノードから
そのノードの１つの子ノードにしか送ることができない。
情報を一番早く木全体に伝わるように伝えた場合、時間はどれだけかかるだろうか。

解法
頂点vを根とする木で、vの子を C1,C2,C3,...,Cn とする。
また、f(u) = (頂点uを根とする木全体に情報が伝達されるのにかかる時間)　とする。
f(v) = min(f(i) | i = 1,2,3,..,n ) + n
となる。
計算量は、合計人数をNとすると、O(N)である。たぶん。

入力
N
m1 c1 c2 ... cm
m2 c1 c2 ... cm
:
:
mN c1 c2 ... cm

Nは合計人数。続くN行にi(0<=i実装

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1 << 29;
const int MAX_N = 100;
bool G[MAX_N][MAX_N];	//G[i][j] == true  iはjの上司である
int N;			//合計人数

int solve(int p){
	int buka_n = 0;
	int time = INF;
	for(int i = 0; i < N; i++){
		if(G[p][i] == true){
			buka_n++;
			time = min(time, solve(i));
		}
	}
	if(time == INF)
		return 0;
	else
		return time + buka_n;
}
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			G[i][j] = false;
	for(int i = 0; i < N; i++){
		int buka_n;
		scanf("%d", &buka_n);
		for(int j = 0; j < buka_n; j++){
			int p;
			scanf("%d", &p);
			G[i][p] = true;
		}
	}
	printf("%d\n", solve(0));
	return 0;
}