记录编号	332415	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999][网络流24题] 星际转移	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	1.830 s
提交时间	2016-10-28 19:39:39	内存使用	16.49 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#define N 2030
#define INF 0x3f3f3f3f
using namespace std;

int n,m,sum,Time,cnt,Found,k=0,al,flow,i,j;
int p[55],s[55][55],bh[55][N];
int gap[N],gaps[N],l[N][N];
bool v[N];

inline void MakeMap(){
	int i=0,j=0,d=0,x=0,next=0;
	cnt=n*(Time+1)+1;
	for (i=1;i<=n;i++)
		for (j=0;j<=Time;j++)
			bh[i][j]=(i-1)*(Time+1)+1+j;
	for (i=0;i<=Time;i++)	l[0][bh[1][i]]=INF;
	for (i=0;i<=Time;i++)	l[bh[n][i]][cnt]=INF;
	for (i=1;i<=n;i++)
		for (j=1;j<=Time;j++)
			l[bh[i][j-1]][bh[i][j]]=INF;
	for (i=1;i<=m;i++){
		if (s[i][0]==1)	continue;
		d=s[i][1];	next=s[i][2];	x=2;
		for (j=0;j<=Time-1;j++){
			l[bh[d][j]][bh[next][j+1]]=p[i];
			d=next;	x=(x+1)%s[i][0];	if (x==0)	x+=s[i][0];	next=s[i][x];
		}
	}
}

inline int min(int a,int b){return (a<b)?a:b;}
inline void Sap(int x){
	int i=0,mingap=cnt-1,F=al;
	if (x==cnt)	{Found=1;	flow+=al;	return;}
	for (i=0;i<=cnt;i++)
		if (l[x][i]){
			if (gap[i]+1==gap[x]){
				al=min(al,l[x][i]);	Sap(i);
				if (gap[1]>=cnt)	return;
				if (Found)	break;
			}
			mingap=min(mingap,gap[i]);
		}
	if (!Found){
		gaps[gap[x]]--;	if (!gaps[gap[x]])	gap[1]=cnt;
		gaps[gap[x]=mingap+1]++;
		}	else l[x][i]-=al,l[i][x]+=al;
}

inline void Write(){
	int i=0,j=0;
	for (i=0;i<=cnt;i++)
		for (j=0;j<=cnt;j++)
			if (l[i][j]>0)	printf("%d %d %d\n",i,j,l[i][j]);
}

inline bool Work(){
	memset(gap,0,sizeof(gap));	memset(gaps,0,sizeof(gaps));
	memset(l,0,sizeof(l));	k=Time;	gaps[0]=cnt;
	MakeMap();	flow=0;
	//Write();
	while (gap[1]<cnt){
		Found=0;	al=INF;	Sap(0);
	}
	if (flow>=sum)	return 1;	else return 0;
}

inline bool Check(){
	int i=0,t=0,d=0,next=0,x=0,j=0;
	for (i=1;i<=m;i++){
		if (s[i][0]==1)	continue;
		d=s[i][1];	next=s[i][2];	x=2;
		while (x<=s[i][0]){
			l[d][next]=1;
			d=next;	x=x+1;	next=s[i][x];	if (x>n)	break;
		}
		l[s[i][s[i][0]]][s[i][1]]=1;
	}
	gap[0]=t=gap[1]=1;	v[1]=1;
	while (t<=gap[0]){
		for (i=1;i<=n;i++)
		if (l[gap[t]][i]&&i!=gap[t])	
			if (!v[i])	gap[++gap[0]]=i,v[i]=1;
		t++;
	}
	if (!v[n])	return false;	else return true;
}

int main(){
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	scanf("%d%d%d",&n,&m,&sum);
	for (i=1;i<=m;i++){
		scanf("%d%d",&p[i],&s[i][0]);
		for (j=1;j<=s[i][0];j++)	{
			scanf("%d",&s[i][j]);
				if (s[i][j]==-1)	s[i][j]=n+2;	else s[i][j]++;
		}
	}
	n+=2;
	if (!Check())	{printf("0\n");	return 0;}
	for (Time=1;Time<=n*(m+1)*sum*2;Time++)
		if (Work())	{printf("%d\n",Time);	return 0;}
	return 0;
}