「网络流 24 题」分配问题

Posted on | In , ,

有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案，使产生的总效益最大。

题目链接

题解

  • 最大费用最大流直接将边权取反跑最小费用最大流即可

代码

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 10100;
const int INF=1e9+7;

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

struct MCMF
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    int d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

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

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

    bool BellmanFord(int s,int t,int& flow, long long& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edges[G[u][i]];
                if( e.cap > e.flow && d[e.to] > d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t] == 1000000000+2)
            return false;
        flow += a[t];
        cost += (long long)d[t] * (long long)a[t];
        for(int u=t; u!=s; u=edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,long long& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
        return flow;
    }
};

struct MCMF2
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    int d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

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

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

    bool BellmanFord(int s,int t,int& flow, long long& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edges[G[u][i]];
                if( e.cap > e.flow && d[e.to] > d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t] == 1000000000+2)
            return false;
        flow += a[t];
        cost += (long long)d[t] * (long long)a[t];
        for(int u=t; u!=s; u=edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,long long& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
        return flow;
    }
};

int n, c[maxn][maxn];

int main()
{
    MCMF now;
    scanf("%d", &n);
    now.init(n*n+10);
    int st=0, ed=2*n+1;
    for(int i=1;i<=n;i++)
    {
        now.Addedge(st, i,1,0);
        for(int j=1;j<=n;j++)
        {
            scanf("%d", &c[i][j]);
            now.Addedge(i, n+j, 1, c[i][j]);
        }
        now.Addedge(n+i, ed, 1, 0);
    }
    ll ans1=0;
    now.MincostMaxflow(st,ed, ans1);
    now.init(n*n+10);
    for(int i=1;i<=n;i++)
    {
        now.Addedge(st, i,1,0);
        for(int j=1;j<=n;j++)
        {
            now.Addedge(i, n+j, 1, -c[i][j]);
        }
        now.Addedge(n+i, ed, 1, 0);
    }
    ll ans2;
    now.MincostMaxflow(st, ed, ans2);
    printf("%lld\n%lld\n", ans1, -ans2);
}