Libre 6004 「网络流 24 题」圆桌聚餐（网络流，最大流）
Description
假设有来自n个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri。会议餐厅共有m张餐桌，每张餐桌可容纳 ci个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。
试设计一个算法，给出满足要求的代表就餐方案。
Input
文件第1行有2个正整数m和n，m表示单位数，n表示餐桌数。
文件第2行有m个正整数，分别表示每个单位的代表数。
文件第3行有n个正整数，分别表示每个餐桌的容量。
Output
如果问题有解，在文件第1行输出1，否则输出0。
接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要求的方案，只要输出一个方案。
Sample Input
4 5
4 5 3 5
3 5 2 6 4
Sample Output
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
Http
Libre:https://loj.ac/problem/6004
Source
网络流，最大流
解决思路
我们建立一个源点和一个汇点，从源点连边到每一个单位，流量就为该单位的人数。从每一个桌子向汇点连边，流量就为该桌子可以坐下的人数。然后再在每一个单位和每一张桌子之间连边，每一条边的流量都为1，这是为了保证一个单位最多只有一个人坐在一张桌子上。
然后我们跑一边最大流。若最大流的流量等于所有单位人数之和，则说明有解，扫描所有单位连向桌子的边看看残量是否为0，若为0，说明该单位有一人坐到了该桌子，输出该桌子的编号。若最大流的流量小于所有单位人数之和，则说无解。
另：这里用Dinic算法实现最大流，具体可以移步笔者的Dinic算法研究总结
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxN=1001;
const int maxM=maxN*maxN*4;
const int inf=2147483647;
class Edge
{
public:
int u,v,flow;
};
int m,n;
int cnt=-1;
int Head[maxN];
int Next[maxM];
Edge E[maxM];
int depth[maxN];
int cur[maxN];
int Q[maxM];
void Add_Edge(int u,int v,int flow);
bool bfs();
int dfs(int u,int flow);
int main()
{
int pepsum=0;
memset(Head,-1,sizeof(Head));
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)//连接每一个单位与每一张桌子
for (int j=1;j<=n;j++)
Add_Edge(i,j+m,1);
for (int i=1;i<=m;i++)
{
int num;
scanf("%d",&num);//读入单位的人数，同时连接源点和单位
Add_Edge(0,i,num);
pepsum+=num;//累计总人数
}
for (int i=1;i<=n;i++)
{
int num;
scanf("%d",&num);//读入桌子的容量，同时连接桌子与汇点
Add_Edge(i+m,n+m+1,num);
}
int Ans=0;//Dinic求最大流
while (bfs())
{
for (int i=0;i<=n+m+1;i++)
cur[i]=Head[i];
while (int di=dfs(0,inf))
Ans+=di;
}
//cout<<Ans<<endl;
if (Ans<pepsum)//若最大流小于人数，则无解
{
cout<<0<<endl;
return 0;
}
cout<<1<<endl;//否则说明有解，输出解
for (int i=1;i<=m;i++)
{
for (int j=Head[i];j!=-1;j=Next[j])
if ((E[j].v>=m+1)&&(E[j].v<=n+m)&&(E[j].flow==0))
cout<<E[j].v-m<<" ";
cout<<endl;
}
return 0;
}
void Add_Edge(int u,int v,int flow)
{
cnt++;
Next[cnt]=Head[u];
Head[u]=cnt;
E[cnt].u=u;
E[cnt].v=v;
E[cnt].flow=flow;
cnt++;
Next[cnt]=Head[v];
Head[v]=cnt;
E[cnt].u=v;
E[cnt].v=u;
E[cnt].flow=0;
}
bool bfs()
{
memset(depth,-1,sizeof(depth));
int h=1,t=0;
Q[1]=0;
depth[0]=1;
do
{
t++;
int u=Q[t];
for (int i=Head[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((depth[v]==-1)&&(E[i].flow>0))
{
depth[v]=depth[u]+1;
h++;
Q[h]=v;
}
}
}
while (h!=t);
if (depth[n+m+1]==-1)
return 0;
return 1;
}
int dfs(int u,int flow)
{
if (u==n+m+1)
return flow;
for (int & i=cur[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((depth[v]==depth[u]+1)&&(E[i].flow>0))
{
int di=dfs(v,min(flow,E[i].flow));
if (di>0)
{
E[i].flow-=di;
E[i^1].flow+=di;
return di;
}
}
}
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
