「网络流24题」 5. 圆桌问题

二分图多重匹配。

多对多。

匈牙利似乎真的不太好办了。

所以乖乖最大流吧。

套路建模，S->每个单位（边权=单位代表数）；每个餐桌->T（边权=餐桌容量）；每个单位->每个餐桌（边权=1）。

跑最大流。

最大流等于总代表数则有解，否则无解。

每个单位的出边中，每条满流边的终点便是这一单位每个代表的餐桌号。

#include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN=430,MAXM=82000; int m,n,S,T,cnt,ans,head[MAXN],cur[MAXN],dis[MAXN]; struct edge { int nxt,to,w; }e[MAXM]; void AddEdge(int u,int v,int w) { e[++cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void AddEdges(int u,int v,int w) { AddEdge(u,v,w); AddEdge(v,u,0); } bool BFS(void) { queue<int> q; memset(dis,0,sizeof dis); q.push(S); dis[S]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u],v;i;i=e[i].nxt) if(e[i].w && !dis[v=e[i].to]) { q.push(v); dis[v]=dis[u]+1; } } return dis[T]; } int DFS(int u,int k) { if(u==T || !k) return k; int t=0; for(int i=head[u],v,f;i;i=e[i].nxt) if(e[i].w && dis[v=e[i].to]==dis[u]+1 && (f=DFS(v,min(k,e[i].w)))) { cur[u]=i; e[i].w-=f; e[((i-1)^1)+1].w+=f; k-=f; t+=f; } if(!t) dis[u]=0; return t; } void Dinic(void) { int f; while(BFS()) while(memcpy(cur,head,sizeof cur),f=DFS(S,INT_MAX)) ans-=f; } void Print(void) { printf("1\n"); for(int u=1;u<=m;++u) { for(int i=head[u],v;i;i=e[i].nxt) if((v=e[i].to) && !e[i].w) printf("%d ",v-m); printf("\n"); } } int main(int argc,char *argv[]) { scanf("%d %d",&m,&n); T=m+n+1; for(int i=1,w;i<=m;++i) { scanf("%d",&w); ans+=w; AddEdges(S,i,w); for(int j=1;j<=n;++j) AddEdges(i,j+m,1); } for(int i=1,w;i<=n;++i) { scanf("%d",&w); AddEdges(i+m,T,w); } Dinic(); if(ans) printf("0\n"); else Print(); return 0; }

谢谢阅读

转载于:https://www.cnblogs.com/Capella/p/8244737.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97474294

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。