记录编号	551310	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2020-05-21 21:51:07	内存使用	13.83 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int head[5001],to[10001],nxt[10001],val[10001];
int dep[10001];
int n,m,S,T,tot=1,a1,a2,MX=0;
void ADD(int x,int y,int z)
{
	to[++tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
	to[++tot]=x;
	val[tot]=0;
	nxt[tot]=head[y];
	head[y]=tot;
}
bool BFS()
{
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(S);
	dep[S]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i])
		{
			if(val[i]&&!dep[to[i]])
			{
				dep[to[i]]=dep[x]+1;
				q.push(to[i]);
				if(to[i]==T)
					return 1;
			}
		}
	}
	return 0;
}
int DFS(int x,int flow)
{
	if(x==T)
	{
		return flow;
	}
	int rest=flow,k;
	for(int i=head[x];i&&rest;i=nxt[i])
	{
		if(val[i]&&dep[to[i]]==dep[x]+1)
		{
			k=DFS(to[i],min(rest,val[i]));
			if(!k)
			{
				dep[to[i]]=0;
			}
			val[i]-=k;
			val[i^1]+=k;
			rest-=k;
		}
	}
	return flow-rest;
}
int Dinic()
{
	int PDS=0,flows;
	while(BFS())
	{
		while(flows=DFS(S,0x3f3f3f3f))
		{
			PDS+=flows; 
		}
	}
	return PDS;
}
int main()
{
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w",stdout);
	scanf("%d%d",&m,&n);
	S=4999;
	T=5000;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a1);
		ADD(S,i,a1);
		MX+=a1;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a1);
		for(int j=1;j<=a1;j++)
		{
			scanf("%d",&a2);
			ADD(a2,i+m,1);
		} 
	}
	for(int i=1;i<=n;i++)
	{
		ADD(i+m,T,1);
	}
	if(Dinic()!=MX)
	{
		puts("NoSolution!");
		return 0;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d:",i);
		for(int j=head[i];j;j=nxt[j])
		{
			if(to[j]!=S&&!val[j])
			{
				printf(" %d",to[j]-m);
			}
		}
		printf("\n");
	}
	return 0;
}