圆桌问题

题目描述

题解：

最大流。

建图即$S$向各单位建边，容量为单位人数；

各单位向所有餐桌建边，容量都为$1$，指每张桌只能有一个人来自这个单位；

所有餐桌向$T$建边，容量为餐桌容量。

若最后得到的最大流为总人数，代表所有人都吃上饭了。

就可以遍历出边输出了。

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 300
#define M 200
#define ll long long
const int inf = 0x3f3f3f3f;
const ll Inf  = 0x3f3f3f3f3f3f3f3fll;
inline int rd()
{
    int f=1,c=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}
    return f*c;
}
int n,m,S,T,a[4*N],b[4*N],hed[4*N],cur[4*N],cnt=-1;
struct EG
{
    int to,nxt;
    ll w;
}e[N*M*8];
void ae(int f,int t,ll w)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    e[cnt].w = w;
    hed[f] = cnt;
}
int dep[N*4];
queue<int>q;
bool vis[N*4];
bool bfs()
{
    memset(dep,0x3f,sizeof(dep));
    memcpy(cur,hed,sizeof(cur));
    q.push(S);dep[S]=0;vis[S] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int j=hed[u];~j;j=e[j].nxt)
        {
            int to = e[j].to;
            if(e[j].w&&dep[to]>dep[u]+1)
            {
                dep[to] = dep[u]+1;
                if(!vis[to])
                {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
        vis[u] = 0;
    }
    return dep[T]!=inf;
}
ll dfs(int u,ll lim)
{
    if(u==T||!lim)return lim;
    ll fl = 0,f;
    for(int j=cur[u];~j;j=e[j].nxt)
    {
        cur[u] = j;
        int to = e[j].to;
        if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].w))))
        {
            fl+=f;
            lim-=f;
            e[j].w-=f;
            e[j^1].w+=f;
            if(!lim)break;
        }
    }
    return fl;
}
ll dinic()
{
    ll ret = 0;
    while(bfs())
        ret+=dfs(S,Inf);
    return ret;
}
int main()
{
    m = rd(),n = rd(),S = n+m+1,T = n+m+2;
    memset(hed,-1,sizeof(hed));
    ll sum = 0;
    for(int i=1;i<=m;i++)
    {
        b[i] = rd();
        sum+=b[i];
        ae(S,i,b[i]);
        ae(i,S,0);
    }
    for(int i=1;i<=n;i++)
    {
        a[i] = rd();
        ae(i+m,T,a[i]);
        ae(T,i+m,0);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=1;j--)
        {
            ae(i,j+m,1);
            ae(j+m,i,0);
        }
    }
    ll tmp = dinic();
    if(tmp==sum)
    {
        puts("1");
        for(int i=1;i<=m;i++)
        {
            for(int j=hed[i];~j;j=e[j].nxt)
            {
                int to = e[j].to;
                if(to==S)continue;
                to-=m;
                if(!e[j].w)printf("%d ",to);
            }
            puts("");
        }
    }else puts("0");
    return 0;
}