记录编号	478092	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 试题库	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-12-08 16:57:54	内存使用	0.85 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxk=20+5;
const int maxn=1000+5;
const int maxsiz=maxn+maxk;
const int inf=0x3f3f3f3f;
namespace io{
    const int L=(1<<19)+1;
    int f;
    char ibuf[L],*iS,*iT,c;
    inline char Gc(){
        if(iS==iT){
            iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
            return iS==iT?EOF:*iS++;
        }
        return*iS++;
    }
    template<class I>void Gi(I&x){
        for(f=1,c=Gc();c<'0'||c>'9';c=Gc())if(c=='-')f=-1;
        for(x=0;c<='9'&&c>='0';c=Gc())x=x*10+(c&15);x*=f;
    }
};
using io::Gi;
inline int readInt()
{
    char c;int tmp=0,x=1;c=getchar();
    while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
    while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
    return tmp*x;
}
int n,k,m,S,T,siz[maxk];
vector<int > typ[maxn];
struct edge{
    int to,cap,rev;
    edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxsiz];
void addedge(int u,int v,int C)
{
    g[u].push_back(edge(v,C,(int)g[v].size()));
    g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int dis[maxsiz],cur[maxsiz],q[maxsiz+5],N;
bool bfs(int st,int ed)
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int head=0,tail=0;
    q[head]=st;
    while(head<=tail) {
        int u=q[head%N];head++;
        for(int i=0;i<(int)g[u].size();i++) {
            edge& e=g[u][i];
            if(e.cap>0 && dis[e.to]==-1) {
                dis[e.to]=dis[u]+1;
                tail++;q[tail%N]=e.to;
            }
        }
    }
    return dis[ed]!=-1;
}
int dfs(int v,int ed,int mf)
{
    if(v==ed) return mf;
    for(int &i=cur[v];i<(int)g[v].size();i++) {
        int u=g[v][i].to;
        edge& e=g[v][i];
        if(e.cap>0 && dis[u]==dis[v]+1) {
            int F=dfs(u,ed,min(mf,e.cap));
            if(F>0) {
                g[v][i].cap-=F;
                g[u][g[v][i].rev].cap+=F;
                return F;
            }
        }
    }
    return 0;
}
int maxF(int st,int ed)
{
    int ret=0,tmp=0;
    while(bfs(st,ed)) {
        memset(cur,0,sizeof(cur));
        while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
    }
    return ret;
}
int main()
{
    freopen("testlib.in","r",stdin);
    freopen("testlib.out","w",stdout);
    Gi(k),Gi(n);
    S=0,T=k+n+1,N=T+2;
    for(int i=1;i<=k;i++) {
        Gi(siz[i]),m+=siz[i];
        addedge(S,i,siz[i]);
    }
    int p,x;
    for(int i=1;i<=n;i++) {
        Gi(p);
        for(int j=1;j<=p;j++) Gi(x),typ[i].push_back(x);
    }
    for(int i=1;i<=n;i++) {
        for(int j=0;j<(int)typ[i].size();j++) {
            int t=typ[i][j];
            addedge(t,k+i,1);
        }
    }
    for(int i=1;i<=n;i++)  addedge(k+i,T,1);
    int res=maxF(S,T);
    if(res<m) printf("NoSolution!\n");
    else {
        for(int i=1;i<=k;i++) {
            printf("%d:",i);
            for(int j=0;j<(int)g[i].size();j++) {
                if(g[i][j].cap==0 && g[i][j].to>k) printf(" %d",g[i][j].to-k);
            }printf("\n");
        }
    }
    return 0;
}