「网络流 24 题」圆桌聚餐 最大流

Posted on | In , ,

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

题目链接

题解

  • 朴素的建图跑最大流即可
  • 方案….??

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 40005;
const int INF=1e9+7;



// Dinic(最大流算法)

struct Edge
{
    int from, to, cap, flow;
    Edge(int u,int v,int c,int f):from(u), to(v), cap(c), flow(f) {}
};


struct Dinic
{
    int n, m, s, t;       // 节点数,边数(包括反向弧),源点编号和汇点编号
    vector<Edge> edges;   // 边数。edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    bool vis[maxn];       // BFS使用
    int d[maxn];          // 从起点到i的距离
    int cur[maxn];        // 当前弧下标

    void init()
    {
        for(int i=0; i<=n; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();
            Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow) //只考虑残量网络中的弧
                {
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0) return a;
        int flow=0, f;
        for(int& i=cur[x]; i<G[x].size(); i++) // 从上次考虑的弧
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1 == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t)
    {
        this->s=s; this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
};

int n, m, r[maxn], c[maxn];
Dinic now;
int main()
{
    scanf("%d%d", &m, &n);
    int st=0, ed=n*100+1;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d", &r[i]);
        now.Addedge(st, i, r[i]);
        sum+=r[i];
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &c[i]);
        now.Addedge(i+m,ed,c[i]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            now.Addedge(i, j+m, 1);
        }
    }
    int ans=now.Maxflow(st,ed);
    printf("%d\n%d\n", sum,ans);
}