关于网络流解决二分图问题,输出具体方案,看一下残量图的边==0 ?就好
#include <iostream> #include<cmath> #include <queue> #include <cstring> using namespace std; const int N =1e4,M=5e5+100; const int inf =1e9+7; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T,n,m; int dis[N],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<N;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } signed main(){ int i,j,x,Cnt=0; cin>>n>>m; S=0,T=n+m+1; for(i=1;i<=n;i++) cin>>x,Cnt+=x,add_(S,i,x); for(i=1;i<=n;i++) for(j=1;j<=m;j++) add_(i,j+n,1); for(i=1;i<=m;i++) cin>>x,add_(i+n,T,x); int ans=0; while(bfs()) ans+=dfs(S,inf); if(ans==Cnt) cout<<1;else cout<<0;cout<<endl; if(ans==Cnt){ for(i=1;i<=n;cout<<endl,i++) for(j=hd[i];j;j=nxt[j]){ int y=go[j]; if(y!=S && w[j]==0&&w[j^1]>0) cout<<y-n<< ' '; } } }