p1694.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 210;
int g[MAXN],gl[MAXN];
int a[MAXN][MAXN];
int M,deep;
int dfs(int lv,int r){
	if(g[r] == 0) return 1;
	int t[MAXN];
	for(int i = 0;i < g[r];++i)
		t[i] = dfs(lv+1,a[r][i]);
	sort(t,t+g[r]);
//	printf("r=%d	",r);
//	for(int i = 0;i < g[r];++i) printf("%d ",t[i]);
	int ans(0);
	for(int i = 0;i < g[r];++i)
		ans = max(ans,t[i]+g[r] - i - 1);
//	printf("ans=%d\n",ans);
	return ans;
}
int main(){
	cin >> M;
	for(int I = 0;I < M;++I){
		int ans(0),n;
		memset(gl,0,sizeof(gl));
		deep = 0;
		cin >> n;
		for(int i = 1;i <= n;++i){
			int t,m;
			scanf("%d",&t);
			scanf("%d",&g[t]);
			for(int j = 0;j < g[t];++j)
				scanf("%d",&a[t][j]);
		}
		cout << dfs(0,1) << endl;
/*		for(int i = 0;i <= deep;++i){ 
			printf("lv %d deep = %d ",i,gl[i]);
			for(int j = 0;j < gl[i];++j)
				printf("%d ",f[i][j]);
			puts("");
		}*/
	}
}