FLOW5 圆桌问题

模型：

二分图多重匹配->网络最大流

题意：

假设有来自 $n$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$ 。会议餐厅共有 $m$ 张餐桌，每张餐桌可容纳 $c_i$ 个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。 试给出满足要求的代表就餐方案。

题解：

将“人”看成本问题中的“流”

显然的，“人”是从“单位”流出，在一张餐桌上汇合的

因此从源点向每个单位连条容量为单位人数的边，从每张桌子向汇点连条容量为桌子容量的边

而桌子与对应单位的边的容量为1（因为一张桌子一个单位至多一人）

跑一遍最大流，用超级汇点统计一下能放的人数，不等于餐桌可容纳人数总数的话就代表是不合法的

然后在残量网络里继续处理

枚举桌子，再依次枚举单位，看看对应的边上有无流量，这对应着这张桌子上有没有这个单位的人

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int oo=0x3f3f3f3f;
const int N=505,M=1e5+5;
int en=1,h[N],d[N],n,m,s,t,use,cur[N],ans,ma;
bool v[N];

struct edge{
    int n,v,f;
}e[N+M<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

void exadd(int x,int y,int z){
    add(x,y,z);
    add(y,x,0);
}

bool bfs(int s,int aim){
    memset(d,0,sizeof d);
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].f){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].f){
            int flow=dfs(y,min(rest,e[i].f),aim);
            rest-=flow;
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}

signed main(){
    read(m);read(n);
    s=1,t=m+n+2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            exadd(i+s,j+s+n,1);
    for(int i=1,x;i<=m;i++)
        exadd(i+s+n,t,read(x)),ma+=x;
    for(int i=1,x;i<=n;i++)
        exadd(s,i+s,read(x));
    if(dinic(s,t)^ma){
        write(0);
        return 0;
    }
    write(1);
    for(int i=1;i<=m;i++){
        puts("");
        int x=i+s+n;
        for(int i=h[x];i;i=e[i].n) if(e[i].f)
            write(e[i].v-s),putchar(' ');
    }
}