记录编号	85310	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999][网络流24题] 星际转移	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2014-01-01 16:06:40	内存使用	1.32 MiB

#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using std::queue;
using std::vector;

const int MAXN=50000;
const int INF=10000000;

struct edge{
	int from,to,cap,flow;
	edge(int fr,int t,int c,int fl):from(fr),to(t),cap(c),flow(fl){}
};

inline int min(int a,int b){
	return a>b?b:a;
}

struct dinic{
	int n,m,s,t;
	vector<edge> edges;
	vector<int> G[MAXN];
	
	bool vis[MAXN];
	int d[MAXN];
	int cur[MAXN];
	
	bool bfs(){
		memset(vis,0,sizeof(vis));
		queue<int> Q;
		Q.push(s);d[s]=0;vis[s]=true;
		while(!Q.empty()){
			int u=Q.front();Q.pop();
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(!vis[e.to] && e.cap>e.flow){
					d[e.to]=d[u]+1;
					vis[e.to]=true;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	
	int dfs(int x,int a){
		if(x==t || a==0)return a;
		int flow=0,f;
		for(int& i=cur[x];i<G[x].size();i++){
			edge &e=edges[G[x][i]];
			if(d[x]+1==d[e.to] && (f=dfs(e.to,min(a,e.cap-e.flow)))>0){
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a==0)return flow;
			}
		}
		return flow;
	}
	
	void add_edge(int from,int to,int cap){
		//printf("from:%d to:%d cap:%d\n",from,to,cap);
		edges.push_back(edge(from,to,cap,0));
		edges.push_back(edge(to,from,0,0));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	void init(int n){
		this->n=n;
		for(int i=0;i<=n;i++)G[i].clear();
		edges.clear();
	}
	
	int max_flow(int s,int t){
		this->s=s;this->t=t;
		int flow=0;
		while(bfs()){
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INF);
		}
		return flow;
	}
};

const int MAXM=50;
struct ship{
	int ren_n;
	int zhan_n;
	int zhan[MAXM];
}ships[MAXM];
int N,M,K;
void read(){
	//int n,m,k;// n（太空站个数20）、 m（太空船个数13）、 k（需要运送的地球上的人的个数50）；
	scanf("%d %d %d",&M,&N,&K);	
	//靠靠靠靠
	for(int i=0;i<N;i++){
		scanf("%d %d",&ships[i].ren_n,&ships[i].zhan_n);
		for(int j=0;j<ships[i].zhan_n;j++)scanf("%d",&ships[i].zhan[j]);
	}
}

dinic solver;

bool check(int day){
	day+=1; 
	solver.init(M*day+day+1);
	solver.add_edge(0,1,K);
	for(int i=1;i<day;i++)solver.add_edge(i,i+1,INF);
	for(int i=1;i<=M;i++)for(int j=1;j<day;j++)solver.add_edge(j+i*day,j+i*day+1,INF);
	for(int i=0;i<N;i++){
		int count=2;
		ship &ts=ships[i];
		int last_z=ts.zhan[0];
		if(last_z==-1)last_z=M*day*day+1;
		else last_z=last_z*day+1;
		for(int j=1;count<=day;j=(j+1)%ships[i].zhan_n){
			if(ts.zhan[j]==-1){
				solver.add_edge(last_z,M*day+day+1,ts.ren_n);
				last_z=M*day+day+1;
			}else {
				solver.add_edge(last_z,(ts.zhan[j])*day+count,ts.ren_n);
				last_z=(ts.zhan[j])*day+count;
			}
			count++;
		}
	}
	solver.t=M*day+day+1;
	if(solver.max_flow(0,solver.t)==K)return true;
	else return false;
}

int solve(){
	read();	
	int left=1,right=150;////
	
	while(left<right){
		int mid=(left+right)/2;
		if(check(mid))right=mid;
		else left=mid+1;
	}
	//if(!check(left))left--;
	if(left==150)left=0;
	return left;
}
void open(){
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
}
int main(){
	open();
	int ans=solve();
	printf("%d",ans);
	return 0;
}