记录编号	430582	评测结果	AAAAAAAAAAA
题目名称	[POI 1999] 洞穴探险	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-30 06:47:17	内存使用	0.00 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,flow,n;
}a[40001];
int pre[201],tot;
inline void insert(int s,int e,int flow){
	a[tot].e=e;
	a[tot].flow=flow;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n;
int ans(0),inf(0xfffffff);
int dis[201];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].flow){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==n)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].flow){
			f=dfs(e,my_min(tmp,a[i].flow));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].flow-=f;
			a[i^1].flow+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline int gg(){
	freopen("gro.in","r",stdin);
	freopen("gro.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read();
	for(int i=1;i<n;i++){
		int x(read());
		for(int j=1;j<=x;j++){
			int y(read());
			if(y<=i)
				continue;
			insert(y,i,0);
			if(y==n||i==1)
				insert(i,y,1);
			else
				insert(i,y,inf);
		}
	}
	while(bfs(1,n))
		ans+=dfs(1,inf);
	printf("%d",ans);
}
int K(gg());
int main(){;}