记录编号	223318	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	Menci	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2016-02-09 16:44:37	内存使用	0.32 MiB

#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>

const int MAXK = 20;
const int MAXN = 1000;

struct Node;
struct Edge;

struct Node {
	Edge *firstEdge;
	int level, id;
} nodes[MAXK + MAXN + 2];

struct Edge {
	Node *from, *to;
	int capacity, flow;
	Edge *next, *reversedEdge;

	Edge(Node *from, Node *to, int capacity) : from(from), to(to), capacity(capacity), flow(0), next(from->firstEdge) {}
};

int k, n;
std::vector<int> v[MAXK];

struct Dinic {
	bool makeLevelGraph(Node *s, Node *t, int n) {
		for (int i = 0; i < n; i++) nodes[i].level = 0;

		std::queue<Node *> q;
		q.push(s);
		s->level = 1;

		while (!q.empty()) {
			Node *v = q.front();
			q.pop();

			for (Edge *e = v->firstEdge; e; e = e->next) {
				if (e->flow < e->capacity && e->to->level == 0) {
					e->to->level = v->level + 1;
					if (e->to == t) return true;
					else q.push(e->to);
				}
			}
		}

		return false;
	}

	int findPath(Node *s, Node *t, int limit) {
		if (s == t) return limit;

		for (Edge *e = s->firstEdge; e; e = e->next) {
			if (e->flow < e->capacity && e->to->level == s->level + 1) {
				int flow = findPath(e->to, t, std::min(e->capacity - e->flow, limit));
				if (flow > 0) {
					e->flow += flow;
					e->reversedEdge->flow -= flow;
					return flow;
				}
			}
		}

		return 0;
	}

	int operator()(int s, int t, int n) {
		int ans = 0;
		while (makeLevelGraph(&nodes[s], &nodes[t], n)) {
			int flow;
			while ((flow = findPath(&nodes[s], &nodes[t], INT_MAX)) > 0) ans += flow;
		}

		return ans;
	}
} dinic;

inline void addEdge(int from, int to, int capacity) {
	nodes[from].firstEdge = new Edge(&nodes[from], &nodes[to], capacity);
	nodes[to].firstEdge = new Edge(&nodes[to], &nodes[from], 0);

	nodes[from].firstEdge->reversedEdge = nodes[to].firstEdge, nodes[to].firstEdge->reversedEdge = nodes[from].firstEdge;
}

int main() {
	freopen("testlib.in", "r", stdin);
	freopen("testlib.out", "w", stdout);

	scanf("%d %d", &k, &n);

	for (int i = 0; i < n + k + 2; i++) nodes[i].id = i;

	const int s = 0, t = n + k + 1;

	int sum = 0;
	for (int i = n + 1; i <= n + k; i++) {
		int x;
		scanf("%d", &x);
		sum += x;

		addEdge(i, t, x);
	}

	for (int i = 1; i <= n; i++) {
		int m;
		scanf("%d", &m);

		for (int j = 0; j < m; j++) {
			int x;
			scanf("%d", &x);
			addEdge(i, n + x, 1);
		}

		addEdge(s, i, 1);
	}

	int maxFlow = dinic(s, t, n + k + 2);
	if (maxFlow == sum) {
		for (int i = 1; i <= n; i++) {
			for (Edge *e = nodes[i].firstEdge; e; e = e->next) {
				if (e->to->id > n && e->to->id <= n + k && e->flow == e->capacity) {
					v[e->to->id - n - 1].push_back(i);
				}
			}
		}
		
		for (int i = 0; i < k; i++) {
			std::sort(v[i].begin(), v[i].end());

			printf("%d:", i + 1);
			for (std::vector<int>::const_iterator p = v[i].begin(); p != v[i].end(); p++) {
				printf(" %d", *p);
			}

			putchar('\n');
		}
	} else puts("NoSolution!");

	fclose(stdin);
	fclose(stdout);

	return 0;
}