首页 > 代码库 > 网络流24题 第五题 - PowerOJ1740 CodeVS1905 圆桌问题 二分图多重匹配 网络最大流
网络流24题 第五题 - PowerOJ1740 CodeVS1905 圆桌问题 二分图多重匹配 网络最大流
欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - PowerOJ1740 - 有SPJ - 推荐
题目传送门 - CodeVS1905 - 无SPJ - 0% 通过率（可以用来看题目）
题意概括
有n支队伍，m个组。第i支队伍有a[i]个人，第i个组最多可以有b[i]个人。
现在要求任何两个同队队员不可位于同一组，求是否有方案满足。
输出第一行，表示是否有，如果有，是1，没有的话，输出0；
如果有，接下来n行，第i行a[i]个数，表示第i支队伍的每个人被安排的组号。
有SPJ，只要输出任意一种方案即可。
题解
其实就是一个网络流的水题。
前置技能 - 网络流（传送门）
对于n支队伍，每只队伍一个点；对于m个组（餐桌），每个组一个点。
另外地，建立一个源点和一个汇点。
连接源点和队伍点，对于队伍i，该边的容量为a[i]；
连接每一个组的点和汇点，对于组i，该边的容量为b[i]；
对于每一个队伍，向每个组连一条边，容量为1。
那么图就构建完了。
至于证明，不解释了。
然后跑一跑最大流，就算出了最大匹配数。
其实，我们可以发现，这是一个二分图多重匹配问题。
如果无法全部匹配，则输出0，
否则输出1，再考虑。
然后对于连接二分图左右两端的边，如果容量为1，那么这条边就是被选择的，那么该边所连接的两个节点，“队伍点”对应“组点”，然后这样就可以把所有的匹配全部还原。
具体操作见代码。
代码
#include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> using namespace std; const int N=450,M=N*N,Inf=1<<25; struct Edge{int x,y,cap,flow,nxt,flag;}; struct Graph{ int cnt,s,t,n,fst[N],dist[N],cur[N],num[N],p[N],head,tail,q[N]; Edge e[M]; void set(int S,int T,int nn){ s=S,t=T,n=nn,cnt=1,memset(fst,0,sizeof fst); } void add(int a,int b,int c,int d){ e[++cnt].x=a,e[cnt].y=b,e[cnt].cap=c,e[cnt].flow=0,e[cnt].flag=d,e[cnt].nxt=fst[a],fst[a]=cnt; e[++cnt].x=b,e[cnt].y=a,e[cnt].cap=0,e[cnt].flow=0,e[cnt].flag=0,e[cnt].nxt=fst[b],fst[b]=cnt; } void re_bfs(){ memset(dist,-1,sizeof dist); memset(q,0,sizeof q); head=tail=dist[t]=0; q[++tail]=t; while (head<tail) for (int x=q[++head],i=fst[x];i;i=e[i].nxt) if (e[i].cap==0&&dist[e[i].y]==-1) dist[q[++tail]=e[i].y]=dist[x]+1; for (int i=1;i<=n;i++) if (dist[i]==-1) dist[i]=n; } int Augment(int &point){ int ex_Flow=Inf; for (int i=t;i!=s;i=e[p[i]].x) if (ex_Flow>=e[p[i]].cap-e[p[i]].flow) ex_Flow=e[p[i]].cap-e[p[i]].flow,point=e[p[i]].x; for (int i=t;i!=s;i=e[p[i]].x) e[p[i]].flow+=ex_Flow,e[p[i]^1].flow-=ex_Flow; return ex_Flow; } int SAP(){ int x=s,y,MaxFlow=0; memset(num,0,sizeof num); for (int i=1;i<=n;i++) num[dist[i]]++,cur[i]=fst[i]; while (dist[s]<=n){ if (x==t){ MaxFlow+=Augment(x); continue; } bool found=0; for (int i=cur[x];i!=0&&!found;i=e[i].nxt) if (dist[e[i].y]+1==dist[x]&&e[i].cap>e[i].flow) cur[x]=p[e[i].y]=i,x=e[i].y,found=1; if (found) continue; int d=n+1; for (int i=fst[x];i;i=e[i].nxt) if (e[i].cap>e[i].flow) d=min(d,dist[e[i].y]+1); if (!(--num[dist[x]])) return MaxFlow; num[dist[x]=d]++,cur[x]=fst[x]; if (x!=s) x=e[p[x]].x; } return MaxFlow; } }g; int n,m,a[N],b[N],sum=0,mat[N][N]; int main(){ scanf("%d%d",&n,&m); g.set(n+m+1,n+m+2,n+m+2); for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i],g.add(g.s,i,a[i],0); for (int i=1;i<=m;i++) scanf("%d",&b[i]),g.add(i+n,g.t,b[i],0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) g.add(i,j+n,1,1); g.re_bfs(); int Flow=g.SAP(); puts(Flow<sum?"0":"1"); if (Flow<sum) return 0; memset(mat,0,sizeof mat); for (int i=2;i<=g.cnt;i++) if (g.e[i].flag==1&&g.e[i].cap==1&&g.e[i].flow==1){ int x=g.e[i].x,y=g.e[i].y-n; mat[x][++mat[x][0]]=y; } for (int i=1;i<=n;i++) sort(mat[i]+1,mat[i]+mat[i][0]+1); for (int i=1;i<=n;puts(""),i++) for (int j=1;j<=mat[i][0];j++) printf("%d ",mat[i][j]); return 0; }
网络流24题 第五题 - PowerOJ1740 CodeVS1905 圆桌问题 二分图多重匹配 网络最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。