记录编号	142853	评测结果	WWWWWWWWWW
题目名称	[网络流24题] 试题库	最终得分	0
用户昵称	Sasuke	是否通过	未通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-12-11 11:33:31	内存使用	3.07 MiB

#include <cstdio>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int Sz = 1e5, 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];
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, c); head[v] = cnt;
}
 
bool vis[Sz];
int s, t, dis[Sz], cur[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 flow, k, n, m;
int Dinic() {
	while (BFS()) {
		for(int i = s; i <= t; ++i) cur[i] = head[i];
		flow += DFS(s, Inf);
	}
	return flow;
}
 
int main() {
	freopen("testlib.in", "r", stdin);
	freopen("testlib.out", "w", stdout);
	
	scanf("%d %d", &k, &n); 
	s = 0; t = n+k+1;
	for(int i = 1; i <= n; ++i) AddEdge(s, i, 1);
	for(int i = 1, c; i <= k; ++i) 
		scanf("%d", &c), AddEdge(n+i, t, c), m += c;
	for(int i = 1,j, p,c; i <= n; ++i)
		for(scanf("%d", &p), j = 0; j < p; ++j) 
			scanf("%d", &c), AddEdge(i, n+c, 1);
	
	if (Dinic() < m) { puts("NoSolution!"); return 0;}
	
	for(int i = 1; i <= k; ++i) {
		printf("%d: ", i);
		for(int E = head[n+i]; E; E = e[E].Next)
			if (e[E].f < 0) printf("%d ", e[E].v);
		puts("");
	}
}