题面

题目描述

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

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

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

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

输入输出格式

输入格式：

第 \(1\) 行有 \(2\) 个正整数 \(m\) 和 \(n\) ， \(m\) 表示单位数， \(n\) 表示餐桌数， \(1 \leq m \leq 150, 1 \leq n \leq 270\) 。

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

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

输出格式：

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

输入输出样例

输入样例：

输出样例：

思路

经典的网络流题。设一个炒鸡超级源点 \(S\) 和一个超级汇点 \(T\) 。对于每一个单位，从源点向单位编号节点连接流量为单位代表数的流；对于每一个餐桌，从餐桌编号节点向汇点连接流量为餐桌容量的流；对于每一组单位和餐桌，连接流量为 \(1\) 的流。那么若该网络能满流，则可以得出一个可行的方案。统计方案是，只需查询每条边单位和餐桌之间的边是否还有流量即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

int m,n,s,t,sum,ans,dep[455],cur[455];

int cnt=1,top[455],to[90005],cap[90005],nex[90005];

inline int read()

{

    int re=0;

    char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

inline void add_edge(int x,int y,int z)

{

    to[++cnt]=y,cap[cnt]=z,nex[cnt]=top[x],top[x]=cnt;

    to[++cnt]=x,cap[cnt]=0,nex[cnt]=top[y],top[y]=cnt;

}

bool dinic()

{

    memset(dep,0,sizeof dep);

    memset(cur,0,sizeof cur);

    dep[s]=1,cur[s]=top[s];

    queue<int>Q;

    Q.push(s);

    while(!Q.empty())

    {

        int now=Q.front();Q.pop();

        for(int i=cur[now];i;i=nex[i])

            if(cap[i]&&!dep[to[i]])

            {

                dep[to[i]]=dep[now]+1,cur[to[i]]=top[to[i]];

                Q.push(to[i]);

            }

    }

    return dep[t]!=0;

}

int dfs(int now,int flow)

{

    if(now==t) return flow;

    int re=0;

    for(int &i=cur[now];i;i=nex[i])

        if(cap[i]&&dep[to[i]]==dep[now]+1)

        {

            int lzq=dfs(to[i],min(flow,cap[i]));

            if(lzq)

            {

                re+=lzq,flow-=lzq;

                cap[i]-=lzq,cap[i^1]+=lzq;

                if(!flow) break;

            }

        }

    return re;

}

int main()

{

    m=read(),n=read(),s=m+n+1,t=s+1;

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

    {

        int x=read();sum+=x;

        add_edge(s,i,x);

    }

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

    {

        int x=read();

        add_edge(i,t,x);

    }

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

        for(int j=m+n;j>=m+1;j--)

            add_edge(i,j,1);

    while(dinic()) ans+=dfs(s,INT_MAX);

    if(ans!=sum) printf("0");

    else

    {

        puts("1");

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

        {

            for(int j=top[i];j;j=nex[j])

            {

                if(j&1) continue;

                if(!cap[j]) printf("%d ",to[j]-m);

            }

            puts("");

        }

    }

    return 0;

}

巴特西

Luogu P3254 圆桌问题(最大流)

题面