网络流24题之五圆桌问题

填坑

«问题描述：

假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为
ri(i=1,2,3…m), 。会议餐厅共有n张餐桌，每张餐桌可容纳c i(i=1,2…n) 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，
给出满足要求的代表就餐方案。

«编程任务：

对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。

«数据输入：

由文件roundtable.in提供输入数据。文件第1行有2 个正整数m和n，m表示单位数，n表
示餐桌数，1<=m<=150, 1<=n<=270。文件第2 行有m个正整数，分别表示每个单位的代表
数。文件第3 行有n个正整数，分别表示每个餐桌的容量。

«结果输出:

程序运行结束时，将代表就餐方案输出到文件roundtable.out中。如果问题有解，在文件第
1 行输出1，否则输出0。接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要
求的方案，只要输出1 个方案。
输入文件示例输出文件示例

roundtable.in

4 5
4 5 3 5
3 5 2 6 4

roundtable.out

模型

二分图多重匹配问题，可以用最大流解决。

实现

建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。

1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。
2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。
3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。

求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。

分析

对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。

代码：

注意 cogs 需要写文件！

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 500001
#define N 500
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
struct node
{
    int from,to,next,flow;
}e[M];
int tot=-1,st[M],dis[N];
int n,m,x,y,z;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z)
{add(x,y,z),add(y,x,0);}
int bfs(int s,int t)
{
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=st[x];~i;i=e[i].next)
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            return ans;
        }
    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
//memset(e,-1,sizeof e);
//memset(st,-1,sizeof st);
main()
{
    freopen("roundtable.in","r",stdin);
    freopen("roundtable.out","w",stdout);
    int a[N],c[N],sum=0;
    scanf("%d%d",&m,&n);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    int S=0,T=n+m+1;
    for (int i=1;i<=m;i++)
        scanf("%d",&a[i]),add_edge(S,i,a[i]),sum+=a[i];
    for (int i=1;i<=n;i++)
        scanf("%d",&c[i]),add_edge(i+m,T,c[i]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            add_edge(j,i+m,1);
    if (Dinic(S,T)!=sum)
        puts("0");
    else
    {
        puts("1");
        for (int i=1;i<=m;i++)
        {
            int path[N],cnt=0;
            for (int j=st[i];~j;j=e[j].next)
                if (e[j].flow==0)
                    path[++cnt]=e[j].to-m;
            for (int j=cnt;j>=1;j--)
                printf("%d ",path[j]);
            puts("");
        }

    }

}

网络流24题之五 圆桌问题

网络流24题之五圆桌问题