https://www.luogu.org/problemnew/show/P2763
题解：网络流+最大流
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=2000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int s,t,n,m,k,p,l,r,u,v,w,c; int ans,cnt,flag,temp,sum; int dis[N]; struct node{ int u,v,c; node(){}; node(int form,int to,int cap):u(form),v(to),c(cap){} }; vector<node>edge; vector<int> G[N]; void Addedge(int u,int v,int cap){ edge.push_back({u,v,cap}); edge.push_back({v,u,0}); int sz=edge.size(); G[u].push_back(sz-2); G[v].push_back(sz-1); } bool bfs(int u){ memset(dis,-1,sizeof(dis)); dis[u]=0; queue<int>q; q.push(u); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<G[u].size();i++){ node e=edge[G[u][i]];//cout<<u<<" "<<e.v<<endl; if(dis[e.v]<0&&e.c>0){ dis[e.v]=dis[u]+1; q.push(e.v); } } } return dis[t]>0; } int dfs(int u,int flow){ if(u==t) return flow; int now; for(int i=0;i<G[u].size();i++){ node e=edge[G[u][i]]; if(e.c>0&&dis[u]+1==dis[e.v]&&(now=dfs(e.v,min(flow,e.c)))){ edge[G[u][i]].c-=now; edge[G[u][i]^1].c+=now; return now; } } return 0; } void dinic(){ while(bfs(s)){ int res=0; while(res=dfs(s,INF)){ ans+=res; } } } void init(){ s=0; t=n+k+1; for(int i=s;i<=t;i++)G[i].clear(); edge.clear(); ans=0; sum=0; } int main() { #ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout); #endif //ios::sync_with_stdio(false); //cin.tie(0); //cout.tie(0); //scanf("%d",&t); //int T=0; while(~scanf("%d%d",&k,&n)){ init(); for(int i=1;i<=k;i++){ scanf("%d",&p); Addedge(n+i,t,p); sum+=p; } for(int i=1;i<=n;i++){ scanf("%d",&m); Addedge(0,i,1); for(int j=1;j<=m;j++){ scanf("%d",&c); Addedge(i,n+c,1); } } dinic(); if(ans!=sum){ cout<<"No Solution!"<<endl; continue; } vector<int>out[N]; for(int i=1;i<=n;i++){ for(int j=0;j<G[i].size();j++){ int id=G[i][j];//cout<<id<<endl; if((~id&1)&&!edge[id].c){//cout<<edge[id].v<<endl; out[edge[id].v-n].push_back(edge[id].u); } } } for(int i=1;i<=k;i++){ printf("%d: ",i); for(int j=0;j<out[i].size();j++){ printf("%d%c", out[i][j], " \n"[out[i].size()-1 == j]); } } } #ifdef DEBUG printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif //cout << "Hello world!" << endl; return 0; }
