记录编号	57959	评测结果	AAAAAAAAAAA
题目名称	[POI 1999] 洞穴探险	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2013-04-14 21:55:01	内存使用	0.80 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
const int MAX=251,INF=0x7fffffff;
int n;
int c[MAX][MAX]={0},f[MAX][MAX]={0},h[MAX]={0},e[MAX]={0};
//c为公路流量,f为前置流,h为高度,e为每个点余流,
int min(int a,int b){
	return (a<b)?a:b;
}
void initialize_preflow(void){//初始化,按算导上写的囧
	int i,s;
	s=0;
	for(i=0;i<n;i++){
		h[i]=0;
		e[i]=0;
	}
	h[s]=n;
	for(i=0;i<n;i++){
		if(c[s][i]!=0){//如果有公路
			f[s][i]=c[s][i];
			f[i][s]=-1*c[s][i];
			e[i]=c[s][i];
			e[s]-=c[s][i];
		}
	}
}
void push(int u,int v){//从u往v压
	int cf,df;//cf就是剩余流量,df就是个变量
	cf=c[u][v]-f[u][v];
	if(cf>0){//能压
		df=min(e[u],cf);
		f[u][v]+=df;
		f[v][u]=-1*f[u][v];
		e[u]-=df;
		e[v]+=df;
	}
}
void generic_push_relabel(void){
	initialize_preflow();//初始化
	bool flag=false;
	int i,j,min;
	int s=0,t=n-1;
	while(!flag){
		flag=true;
		for(i=0;i<n;i++){
			if(i==s||i==t) continue;
			if(e[i]>0){//有余流
				min=0xffffff;
				flag=false;
				for(j=0;j<n;j++){
					if(j==i) continue;
					if(c[i][j]-f[i][j]>0){//在残留图中
						if(h[j]==h[i]-1){
							push(i,j);//压
							goto NEXT;
						}
					}
					if(h[j]<min) min=h[i];
				}
				h[i]=min+1;//重标记
			}
			NEXT:;
		}
	}
}
int finalflow(void){
	int t=n-1,sum=0;
	int i;
	for(i=0;i<n;i++){
		if(i==t) continue;
		sum+=f[i][t];
	}
	return sum;
}
int main(){
	freopen("gro.in","r",stdin);
	freopen("gro.out","w",stdout);
	cin>>n;
	int i,j,m,temp;
	for(i=0;i<n-1;i++){
		scanf("%d",&m);
		for(j=0;j<m;j++){
			scanf("%d",&temp);
			//cout<<i+1<<" "<<temp<<endl;
			c[i][temp-1]=(i==0||temp==n)?1:INF;
		}
	}
	/*for(i=0;i<n;i++){
		for(j=0;j<n;j++) cout<<setw(10)<<c[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;*/
	generic_push_relabel();
	int ans;
	ans=finalflow();
	cout<<ans<<endl;
	return 0;
}