LibreOJ 6004. 「网络流 24 题」圆桌聚餐网络流版子题

2022-11-01 18:44:39

#6004. 「网络流 24 题」圆桌聚餐

内存限制：256 MiB时间限制：5000 ms标准输入输出

题目类型：传统评测方式：Special Judge

上传者：匿名

题目描述

假设有来自 n nn 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri r_iri。会议餐厅共有 m mm 张餐桌，每张餐桌可容纳 ci c_ici 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法，给出满足要求的代表就餐方案。

输入格式

文件第 1 11 行有 2 22 个正整数 m mm 和 n nn，m mm 表示单位数，n nn 表示餐桌数。
文件第 2 22 行有 m mm 个正整数，分别表示每个单位的代表数。
文件第 3 33 行有 n nn 个正整数，分别表示每个餐桌的容量。

输出格式

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

样例

样例输入

样例输出

数据范围与提示

1≤m≤150,1≤n≤270 1 \leq m \leq 150, 1 \leq n \leq 2701≤m≤150,1≤n≤270

题目链接：https://loj.ac/problem/6004

思路：最大流板子题

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define PI acos(-1.0)

const int maxn=,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;

const ll INF=1e18+;

struct edge

{

    int from,to,cap,flow;

};

vector<edge>es;

vector<int>G[maxn];

bool vis[maxn];

int dist[maxn];

int iter[maxn];

void init(int n)

{

    for(int i=; i<=n+; i++) G[i].clear();

    es.clear();

}

void addedge(int from,int to,int cap)

{

    es.push_back((edge)

    {

        from,to,cap,

    });

    es.push_back((edge)

    {

        to,from,,

    });

    int x=es.size();

    G[from].push_back(x-);

    G[to].push_back(x-);

}

bool BFS(int s,int t)

{

    memset(vis,,sizeof(vis));

    queue <int> Q;

    vis[s]=;

    dist[s]=;

    Q.push(s);

    while(!Q.empty())

    {

        int u=Q.front();

        Q.pop();

        for (int i=; i<G[u].size(); i++)

        {

            edge &e=es[G[u][i]];

            if (!vis[e.to]&&e.cap>e.flow)

            {

                vis[e.to]=;

                dist[e.to]=dist[u]+;

                Q.push(e.to);

            }

        }

    }

    return vis[t];

}

int DFS(int u,int t,int f)

{

    if(u==t||f==) return f;

    int flow=,d;

    for(int &i=iter[u]; i<G[u].size(); i++)

    {

        edge &e=es[G[u][i]];

        if(dist[u]+==dist[e.to]&&(d=DFS(e.to,t,min(f,e.cap-e.flow)))>)

        {

            e.flow+=d;

            es[G[u][i]^].flow-=d;

            flow+=d;

            f-=d;

            if (f==) break;

        }

    }

    return flow;

}

int Maxflow(int s,int t)

{

    int flow=;

    while(BFS(s,t))

    {

        memset(iter,,sizeof(iter));

        int d=;

        while(d=DFS(s,t,inf)) flow+=d;

    }

    return flow;

}

int a[maxn],b[maxn];

int main()

{

    int n,m;

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

    int s=,t=n+m+;

    init(n+m+);

    int sum=;

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

    {

        for(int j=; j<=m; j++)

            addedge(i,j+n,);

    }

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

    {

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

        sum+=a[i];

        addedge(s,i,a[i]);

    }

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

    {

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

        addedge(i+n,t,b[i]);

    }

    if(Maxflow(s,t)<sum) printf("0\n");

    else

    {

        printf("1\n");

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

        {

            if(es[i].flow>) printf("%d ",es[i].to-n);

            if(es[i].to-n==m) printf("\n");

        }

    }

    return ;

}

最大流版子题

码农公寓