记录编号	430165	评测结果	AAAAAAAAAAA
题目名称	[POI 1999] 洞穴探险	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-07-29 15:00:55	内存使用	0.45 MiB

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int n,map[205][205],num,peo,tot,a,dis[205],q[205],h,t;
bool bfs(){
	 memset(dis,0xff,sizeof(dis));
	 dis[1]=0;h=0;t=1;q[t]=1;
	 while(h<t){
	 	   int k=q[++h];
	 	   for(int i=1;i<=n;i++)
			   if(dis[i]<0&&map[k][i]>0){
			      dis[i]=dis[k]+1;
				  q[++t]=i;
			   }
	}
	if(dis[n]>0) return true;
	else return false;
}
int dfs(int x,int last){
	 if(x==n) return last;
	 for(int i=1;i<=n;i++)
	     if(map[x][i]>0&&dis[i]==dis[x]+1&&(a=dfs(i,min(last,map[x][i])))){
	        map[x][i]-=a;
	        map[i][x]+=a;
	        return a;
	     }
	 return 0;
}
int main(){
	freopen("gro.in","r",stdin);
	freopen("gro.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d",&num);
		for(int j=1;j<=num;j++){ 
		    scanf("%d",&a);
		    if(a<=i) continue;
		    map[i][a]=0x7fffffff;
		}
	}
	for(int i=2;i<=n;i++) if(map[1][i]) map[1][i]=1;//woc!
	for(int i=1;i<n;i++) if(map[i][n]) map[i][n]=1;//woc!他妈读题的重要性 
	while(bfs())
	      while(tot=dfs(1,0x7fffffff))
	            peo+=tot;
	printf("%d",peo);
	return 0;
}