记录编号	62710	评测结果	AAAAAWAAAA
题目名称	[网络流24题] 试题库	最终得分	90
用户昵称	lazycal	是否通过	未通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-07-08 14:29:30	内存使用	28.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=1100,INF=0x7fffffff;
int n,k,ec,cnt[N],dis[N],son[N],sink,src,Vc,flow,tot;
struct node
{
	int link,f,next;
}es[N*N*2];
inline void addedge(const int x,const int y,const int z)
{
	es[ec].next=son[x];
	es[ec].link=y;
	es[ec].f=z;
	son[x]=ec++;
}
inline void Addedge(const int x,const int y,const int z)
{addedge(x,y,z);addedge(y,x,0);}
void init()
{
	memset(son,-1,sizeof son);
	memset(cnt,0,sizeof cnt);
	memset(dis,0,sizeof dis);
	ec=0;
	src=0;sink=n+k+1;cnt[0]=Vc=n+k+2;
}
int sap(const int u,const int aug)
{
	if (u==sink) return aug;
	int mindis=Vc,sum=0;
	for (int i=son[u];i!=-1;i=es[i].next) {
		const int v=es[i].link;
		if (dis[v]+1==dis[u] && es[i].f>0) {
			int t=sap(v,std::min(aug-sum,es[i].f));
			sum+=t; es[i].f-=t; es[i^1].f+=t;
			if (sum==aug || dis[src]>=Vc) return sum;
		}
		if (es[i].f>0 && mindis>dis[v]) mindis=dis[v];
	}
	if (!sum) {
		if (!--cnt[dis[u]]) dis[src]=Vc;
		++cnt[dis[u]=mindis+1];
	}
	return sum;
}
void max_flow(){while (dis[src]<Vc) flow+=sap(src,INF);}
void print()
{
	if (flow!=tot) {puts("No Solution!");return;}
	for (int i=1;i<=k;++i) {
		printf("%d:",i);
		for (int j=son[i];j!=-1;j=es[j].next)
			if (es[j].link!=src && !es[j].f) 
				printf(" %d",es[j].link-k);
		puts("");
	}
}
int main()
{
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w",stdout);
	scanf("%d%d",&k,&n);
	init();
	for (int i=1,x;i<=k;++i) {
		scanf("%d",&x);
		tot+=x;
		Addedge(src,i,x);
	}/*
	for (int i=0;i<=Vc;++i) {
		printf("%d: ",i);
		for (int j=son[i];j!=-1;j=es[j].next) printf("%d ",es[j].link);
		puts("");
		}*/
	for (int i=1,p,x;i<=n;++i) {
		scanf("%d",&p);
		Addedge(i+k,sink,1);
		while (p--) {
			scanf("%d",&x);
			Addedge(x,i+k,1);
		}
	}
	max_flow();
	print();
}