记录编号	484406	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	冷曦	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2018-01-23 20:54:48	内存使用	0.39 MiB

#include<cstdio>
#include<cstring>
const int N=1205;
const int M=30005;
const int inf=1e9+7;
int n,m,k,p,head[N],next[M],to[M],f[M],tot=1,dis,ans,S,T,s[N],d[N],nodes;
bool b[1005];
inline int min(int a,int b){a-=b;return b+(a&(a>>31));}
inline void add(int x,int y,int p)
{
	next[++tot]=head[x];head[x]=tot;to[tot]=y;f[tot]=p;
	next[++tot]=head[y];head[y]=tot;to[tot]=x;f[tot]=0;
}
inline void sap(int x,int y)
{
	if(x==T) {tot=y;return;}
	int sum=0;
	for(int i=head[x];i;i=next[i])
	{
		if(f[i]&&d[x]==d[to[i]]+1)
		{
			sap(to[i],min(f[i],y-sum));
			sum+=tot;f[i]-=tot;f[i^1]+=tot;
			if(d[0]>T||sum==y) {tot=sum;return;}
		}
	}
	if(sum==0)
	{
		if(--s[d[x]])
		{
			dis=nodes;
			for(int i=head[x];i;i=next[i])
				dis=min(dis,d[to[i]]+(T&(f[i]>0)-1));
			++s[d[x]=dis+1];
		}
		else d[0]=nodes;
	}
	tot=sum;return;
}
int main()
{
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w",stdout);
	scanf("%d%d",&k,&n);
	for(int i=1;i<=k;++i)scanf("%d",&T),add(S,i,T),m+=T;
	T=k+n+1;
	for(int i=1;i<=n;++i)
	  {
	  	scanf("%d",&p);
	  	for(int j=1;j<=p;++j)
	  	  scanf("%d",&S),add(S,i,1);
	  	add(i,T,1);
	  }
	S=0;s[0]=nodes=T+1;
	do sap(S,inf),ans+=tot; while(d[S]<nodes);
	if(ans!=m)puts("NoSolution!");
	else
	  for(int i=1;i<=k;++i)
	    {
	      memset(b,false,sizeof(b));
	      printf("%d: ",i);
	      for(int j=head[i];j;j=next[j])
	        if(to[j]&&f[j]==0)b[to[j]]=true;
		  for(int j=1;j<=n;++j)if(b[j])printf("%d ",j);
		  printf("\n");
		}
}