[洛谷P3254] [网络流24题] 圆桌游戏

Description###

假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。

会议餐厅共有n 张餐桌，每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

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

Input###

第1 行有2 个正整数m 和n，m 表示单位数，n 表示餐桌数，1<=m<=150, 1<=n<=270。

第2 行有m 个正整数，分别表示每个单位的代表数。

第3 行有n 个正整数，分别表示每个餐桌的容量。

Output###

如果问题有解，第1 行输出1，否则输出0。接下来的m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案，只要输出1 个方案。

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

想法##

因为是网络流24题，所以上来我先想的是怎么用可爱的最小割。

没想出来，于是仔细分析了一下题意。

发现，诶，好像贪心就可以啊……

单位代表数排个序，每个餐桌剩余容量排个序，先做剩余容量多的餐桌。

就A了……

之后又想了想网络流怎么做。

S向每个单位连容量为单位代表数的边，每个单位向所有餐桌连容量为1的边，每个餐桌向T连容量为餐桌容量的边。

跑一边最大流，看S发出的边是否都满流就完了。

这可真是一道辣鸡题……

代码##

（贪心）

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 275;

const int M = 155;

struct data{

    int v,id;

    bool operator < (const data &b) const{

        return v>b.v;

    }

}d[N],r[M];

int c[M][N],w[M];

int n,m;

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=1;i<=m;i++){

        scanf("%d",&r[i].v);

        r[i].id=i;

        w[i]=r[i].v;

    }

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

        scanf("%d",&d[i].v);

        d[i].id=i;

    }

    int flag=1;

    sort(r+1,r+1+m);

    for(int i=1;i<=m;i++){

       sort(d+1,d+1+n);

       for(int j=1;j<=r[i].v;j++){

           if(!d[j].v) break;

           c[r[i].id][j]=d[j].id;

           d[j].v--;

       }

       if(!c[r[i].id][r[i].v]) { flag=0; break; }

    }

    if(flag==0) printf("0\n");

    else {

        printf("1");

        for(int i=1;i<=m;i++){

            printf("\n%d",c[i][1]);

            for(int j=2;j<=w[i];j++)

                printf(" %d",c[i][j]);

        }

    }

    return 0;

}

巴特西