记录编号	587158	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-03-16 17:55:19	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=1<<29;
const int maxn=1100,maxm=44000;
int h[maxn],v[maxm],ne[maxm],e[maxm],d[maxn],now[maxn];
int n,k,m=0,s,t,tot,maxflow;
void add(int x,int y,int z)
{
    tot++;
    v[tot]=y;
    e[tot]=z;
    ne[tot]=h[x];
    h[x]=tot;
    tot++;
    v[tot]=x;
    e[tot]=0;
    ne[tot]=h[y];
    h[y]=tot;
}
int bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s);
    d[s]=1;
    now[s]=h[s];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=ne[i])
        {
            int y=v[i];
            if(e[i]&&d[y]==0)
            {
                q.push(y);
                now[y]=h[y];
                d[y]=d[x]+1;
                if(y==t)
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)
    {
        return flow;
    }
    int rest=flow;
    int k;
    for(int i=now[x];i&&rest;i=ne[i])
    {
        now[x]=i;
        int y=v[i];
        if(e[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,e[i]));
            if(k==0)
            {
                d[y]=0;
            }
            e[i]-=k;
            e[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int main()
{
    freopen("testlib.in","r",stdin);
    freopen("testlib.out","w",stdout);
    scanf("%d%d",&k,&n);
    s=0;
    t=n+k+1;
    for(int i=1;i<=k;i++)
    {
        int a;
        scanf("%d",&a);
        m+=a;
        add(s,i+n,a);
    }
    for(int i=1;i<=n;i++)
    {
        int p;
        scanf("%d",&p);
        for(int j=1;j<=p;j++)
        {
            int b;
            scanf("%d",&b);
            add(b+n,i,1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        add(i,t,1);
    }
    int flow=0;
    while(bfs())
    {
        while(flow=dinic(s,inf))
        {
            maxflow+=flow;
        }
    }
    if(maxflow==m)
    {
        for(int i=1+n;i<=n+k;i++)
        {
            printf("%d: ",i-n);
            for(int j=h[i];j;j=ne[j])
            {
                if(e[j]==0)
                {
                    printf("%d ",v[j]);
                } 
            }
            printf("\n");
        }
    }
    else
    {
        cout<<"NoSolution!";
    }
    return 0;
}