首页 > 代码库 > [网络流24题]圆桌问题

[网络流24题]圆桌问题

2024-08-30 08:06:51   222人阅读

Description

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

Input

第$1$行有$2$个正整数$m,n.m$表示单位数，$n$表示餐桌数。

第$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

HINT

$1\;\leq\;m\;\leq\;150,1\;\leq\;n\;\leq\;270$

Solution

单位$i$为$x_i$,餐桌$i$为$y_i$,建立二分图.

从$s$向$x_i$连接一条容量为$r_i$的有向边,

从$x_i$向$y_j$连接一条容量为$1$的有向边,

从$y_i$向$t$连接一条容量为$c_i$的有向边,

如果最大流=人数和,则有解,从集合$x$从发流向集合$y$的满流边为当前方案.

#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 275
#define M 155
using namespace std;
struct graph{
    int nxt,to,f;
}e[(N*M)<<1];
int a[M],b[N],g[N+M],dep[N+M],n,m,s,t,sum,cnt=1;
queue<int> q;
inline void addedge(int x,int y,int f){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].f=f;
} 
inline void adde(int x,int y,int f){
    addedge(x,y,f);addedge(y,x,0);
}
inline bool bfs(int u){
    memset(dep,0,sizeof(dep));
    dep[u]=1;q.push(u);
    while(!q.empty()){
        u=q.front();q.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(e[i].f>0&&!dep[e[i].to]){
                q.push(e[i].to);
                dep[e[i].to]=dep[u]+1;
            }
    }
    return dep[t];
}
inline int dfs(int u,int f){
    int ret=0;
    if(u==t) return f;
    for(int i=g[u],d;i&&f;i=e[i].nxt)
        if(e[i].f>0&&dep[e[i].to]>dep[u]){
            d=dfs(e[i].to,min(f,e[i].f));
            e[i].f-=d;e[i^1].f+=d;ret+=d;f-=d;
        }
    return ret;
}
inline int dinic(){
    int ret=0;
    while(true){
        if(!bfs(s)) return ret;
        ret+=dfs(s,sum);
    }
}
inline void Aireen(){
    scanf("%d%d",&m,&n);
    s=n+m+1;t=s+1;
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        adde(s,i,a[i]);
        sum+=a[i];
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
        adde(i+m,t,b[i]);
    }
    for(int i=1;i<=m;++i)
        for(int j=n;j;--j)
            adde(i,j+m,1);
    if(dinic()==sum){
        puts("1");
        for(int i=1;i<=m;++i){
            for(int j=g[i];j;j=e[j].nxt)
                if(!(j&1)&&!e[j].f)
                    printf("%d ",e[j].to-m);
            printf("\n");
        }
    }
    else puts("0");
    
}
int main(){
    freopen("table.in","r",stdin);
    freopen("table.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

[网络流24题]圆桌问题


联系
我们