Cogs 729. [网络流24题] 圆桌聚餐

[网络流24题] 圆桌聚餐

★★ 输入文件：roundtable.in 输出文件：roundtable.out 评测插件

时间限制：1 s 内存限制：128 MB

«问题描述：

假设有来自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

1

1 2 4 5

1 2 3 4 5

2 4 5

1 2 3 4 5

/*

二分图多重匹配问题.

最大流.

和前几题做法相似.

建模的时候

从源点到货库建一条流量为库存量的边.

从货库与商店间建一条流量为1的边.

从商店到汇点建一条流量为所需量的边.

dinic即可.

*/

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#define MAXN 10001

using namespace std;

struct data{int v,next,c;}e[MAXN*2];

int n,m,max1=1e9,ans,total,cut=1,dis[MAXN],head[MAXN],next[MAXN];

bool in[MAXN];

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int x)

{

    e[++cut].v=v;

    e[cut].c=x;

    e[cut].next=head[u];

    head[u]=cut;

}

bool bfs()

{

    memset(dis,-1,sizeof dis);

    queue<int>q;

    q.push(0);

    dis[0]=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1&&e[i].c)

            {

                dis[v]=dis[u]+1;

                q.push(v);

            }

        }

    }

    return dis[n+m+1]!=-1;

}

int dfs(int u,int y)

{

    if(u==n+m+1) return y;

    int rest=0;

    for(int i=head[u];i&&rest<y;i=e[i].next)

    {

        int v=e[i].v;

        if(dis[v]==dis[u]+1&&e[i].c)

        {

            int x=dfs(v,min(e[i].c,y-rest));

            rest+=x;

            e[i].c-=x;

            e[i^1].c+=x;

        }

    }

    if(!rest) dis[u]=-1;

    return rest;

}

void print()

{

    for(int u=1;u<=n;u++)

    {

        for(int i=head[u];i;i=e[i].next)

      {

          int v=e[i].v;

          if(!e[i].c) printf("%d ",v-n);

      }

      printf("\n");

    }

}

void dinic(int s,int t)

{

    while(bfs()) ans+=dfs(s,max1);

    if(ans==total) {printf("1\n");print();}

    else printf("0");

    return ;

}

int main()

{

    freopen("roundtable.in","r",stdin);

    freopen("roundtable.out","w",stdout);

    int x,y;

    n=read(),m=read();

    for(int i=1;i<=n;i++) x=read(),total+=x,add(0,i,x),add(i,0,0);

    for(int i=1;i<=m;i++) x=read(),add(n+i,n+m+1,x),add(n+m+1,n+i,0);

    for(int i=1;i<=n;i++)

      for(int j=1;j<=m;j++)

        add(i,n+j,1),add(n+j,i,0);

    dinic(0,n+m+1);

    return 0;

}

巴特西

Cogs 729. [网络流24题] 圆桌聚餐

最新文章

热门文章