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

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int Sz = 1e5 +9, Sz2 = 999, Inf = 1<<30;

struct Edge {
	int v, Next, f, c;
	Edge() {}
	Edge(int v, int n, int f, int c): v(v), Next(n), f(f), c(c) {}
} e[Sz<<1];
int head[Sz], cnt = 1;

void AddEdge(int u, int v, int c) {
	e[++cnt] = Edge(v, head[u], 0, c); head[u] = cnt;
	e[++cnt] = Edge(u, head[v], 0, 0); head[v] = cnt;
}

int n, m, k, h[Sz], r[Sz], rr[Sz2][Sz2];
int ans, s, t, dis[Sz], cur[Sz];
bool vis[Sz];
queue <int> q;

bool BFS() {
	memset(vis, 0, sizeof vis);
	q.push(s); vis[s] = 1; dis[s] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for(int E = head[u], v; E; E = e[E].Next)
			if (!vis[v = e[E].v] && e[E].c>e[E].f)
				q.push(v), vis[v] = 1, dis[v] = dis[u]+1;
	}
	return vis[t];
}

int DFS(int o, int a) {
	if (o==t || !a) return a;
	int flow = 0, f;
	for(int& i = cur[o]; i; i = e[i].Next) {
		Edge& E = e[i];
		if (dis[E.v] == dis[o]+1 && (f = DFS(E.v, min(a, E.c-E.f)))>0) {
			E.f += f; e[i^1].f -= f; flow += f; a -= f;
			if (!a) break;
		}
	}
	return flow;
}

int fa[Sz];
int find(int o) {return fa[o]-o? fa[o] = find(fa[o]): o;}
bool floodfill() {
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 0; i < m; ++i)
		for(int j = 1; j < r[i]; ++j)
			fa[find(rr[i][j])] = find(rr[i][0]);
	return find(1) == find(2);
}

int solve() {
	if (!floodfill()) return 0;
	int flow = 0;
		
	while (++ans) {
		
		for(int i = 0; i < m; ++i)
			AddEdge(ans*n-n+rr[i][(ans-1+r[i])%r[i]], ans*n+rr[i][ans%r[i]], h[i]);
		for(int i = 1; i <= n; ++i) 
			AddEdge(ans*n-n+i, ans*n+i, Inf);
		
		s = 2; t = ans*n+1;
		while (BFS()) {
			for(int i = 1; i <= ans*n; ++i) cur[i] = head[i];
			flow += DFS(s, Inf);
		}
		if (flow >= k) break;
	}
	return ans;
}

int main() {
	freopen("home.in", "r", stdin);
	freopen("home.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &k); n += 2;
	for(int i = 0, j; i < m; ++i) 
		for(scanf("%d %d", h+i, r+i), j = 0; j < r[i]; ++j)
			scanf("%d", rr[i]+j), rr[i][j] += 2;
	printf("%d\n", solve());
}