记录编号	475279	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	雨季	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2017-11-15 11:21:47	内存使用	9.42 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
#define M 1000005
#define N 2005

int k,n,m,S,T;

inline int read() {
	int tmp=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') tmp=tmp*10+ch-'0',ch=getchar();
	return tmp*w;
}

struct node {
	int v,c,nex;
}e[M];
int tot=1,h[N],use[N];
void add(int u,int v,int c) {
	e[++tot].v=v,e[tot].c=c,e[tot].nex=h[u],h[u]=tot;
	e[++tot].v=u,e[tot].c=0,e[tot].nex=h[v],h[v]=tot;
}

int dis[N];
bool vis[N];
queue<int>q;
bool bfs() {
	while(!q.empty()) q.pop();
	for(int i=S;i<=T;++i) vis[i]=0;
	vis[S]=1;
	dis[S]=1;
	q.push(S);
	int x,xx;
	while(!q.empty()) {
		x=q.front();
		q.pop();
		for(int i=h[x];i;i=e[i].nex) {
			xx=e[i].v;
			if(e[i].c&&!vis[xx]) {
				vis[xx]=1;
				dis[xx]=dis[x]+1;
				q.push(xx);
			}
		}
		if(vis[T]) return 1;
	}
	return 0;
}
int dfs(int x,int want) {
	if(x==T||!want) return want;
	int xx;
	int f=0,get=0;
	for(int i=use[x];i;i=e[i].nex) {
		xx=e[i].v;
		if(dis[xx]==dis[x]+1) {
			f=dfs(xx,min(e[i].c,want));
			if(!f) continue;
			e[i].c-=f;
			e[i^1].c+=f;
			want-=f;
			get+=f;
			use[x]=i;
			if(!want) break;
		}
	}
	return get;
}

int main()
{
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w",stdout);
	k=read(),n=read();
	S=0,T=k+n+1;
	int x,p;
	for(int i=1;i<=k;++i) {
		x=read(); // 第i个类型需要的试题
		m+=x;
		add(S,i,x); 
	}
	for(int i=1;i<=n;++i) {
		p=read();
		for(int j=1;j<=p;++j) {
			x=read();
			add(x,i+k,1);
		}
		add(i+k,T,1);
	}//cout<<m<<endl;
//	for(int i=k+1;i<=n;++i) add(i,T,1);
	while(bfs()) {//cout<<"EEEE"<<endl;
		for(int i=S;i<=T;++i) use[i]=h[i];
		m-=dfs(S,1e9);
	}//cout<<m<<endl;
	if(m) {printf("NoSolution!\n");return 0;}
//	for(int i=2;i<=tot;i+=2) cout<<e[i].c<<endl;
	for(int i=1;i<=k;++i) {
		printf("%d:",i);
		for(int j=h[i];j;j=e[j].nex) {
			if(e[j].c==0) printf(" %d",e[j].v-k);
		}printf("\n");
	}
	return 0;
}