记录编号	392055	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999][网络流24题] 星际转移	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2017-04-06 22:19:11	内存使用	12.29 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct edge{int f,t,g;}w[N];
int n,m,k,p,S,T,head[N],next[N],cnt=1;
void add(int f,int t,int g){
	w[++cnt]=(edge){f,t,g};
	next[cnt]=head[f];
	head[f]=cnt;
	w[++cnt]=(edge){t,f,0};
	next[cnt]=head[t];
	head[t]=cnt;
}
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[N];
int l[N],top,ans;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans+=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[z[i].i^1].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=0;i<=p;i++) l[i]=0;
	l[S]=1;Q.push(S);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[T]) return 0;
	z[top=1]=st(S,1e9);
	while (top){
		if (V==T){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
int H[N],r[N],go[1010][1010],id[1010][1010];
void init(int T){
	while (cnt>1) next[cnt--]=0;
	ans=0;p=2;
	for (int i=0;i<=T;i++){
		id[0][i]=0;id[1][i]=1;id[2][i]=2;
		for (int j=1;j<=n;j++) id[j+2][i]=++p;
	}
	for (int i=0;i<=p;i++) head[i]=0;
	for (int i=1;i<=m;i++)
	for (int j=1;j<=T;j++)
		add(id[go[i][j-1]][j-1],id[go[i][j]][j],H[i]);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=T;j++)
		add(id[i+2][j-1],id[i+2][j],1e9);
	add(1,2,k);
}
void solve(int l,int r){
	if (l==r) return void(printf("%d\n",l==1000?0:l));
	int mid=(l+r)>>1;
	init(mid);
	while (dinic());
	if (ans!=k) solve(mid+1,r);else solve(l,mid);
}
int main()
{
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	S=0;T=2;
	for (int i=1;i<=m;i++){
		scanf("%d%d",&H[i],&r[i]);
		for (int j=0;j<r[i];j++){
			scanf("%d",&go[i][j]);
			if (go[i][j]) go[i][j]+=2;
		}
		for (int j=r[i];j<1010;j++) go[i][j]=go[i][j-r[i]];
	}
	solve(1,1000);
	return 0;
}