P4016 负载平衡问题

负载平衡问题

Time Limit: 1000ms, Memory Limits: 256MB
Total Submission: 1.4k, Accepted Submission: 774

题目描述

G 公司有$n$个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使$n$个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

输入输出格式

输入格式

第 1 行中有 1 个正整数 $n$,表示有 $n$ 个仓库。

第 2 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。

输出格式

输出最少搬运量。

输入输出样例

输入样例

5
17 9 14 16 4

输出样例

11

说明

$$ 1 \leq n \leq 100$$


Solution

显然,最终的仓库库存为所有仓库的初始库存的平均值。

先建立超级源点与超级汇点。对于每一个初始库存$a_i$大于平均值$ave$的仓库,与超级源连一条边,流量为$a_i - ave$,费用为0。对于每个初始库存$a_i$小于平均值$ave$的仓库,与超级汇连一条边,流量为$ave - a_i$,费用为0。在所有相邻的两仓库间连一条边,流量为infi, 费用为1。然后跑一遍费用流,结果即为$ans$。

Code

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct edge {
int v, w, c, next;
edge(int vv = 0, int ww = 0, int cc = 0, int nxt = -1) : v(vv), w(ww), c(cc), next(nxt) {}
}G[maxn];

int tot, head[105], cost[105], inq[105], pre[105];

inline void init() {
tot = 0;
memset(head, -1, sizeof head);
}

inline void addedge(int u, int v, int w, int c) {
G[tot] = edge(v, w, c, head[u]); head[u] = tot++;
G[tot] = edge(u, 0, -c, head[v]); head[v] = tot++;
}

bool spfa(int st, int ed) {
memset(pre, -1, sizeof pre);
memset(cost, 0x3f, sizeof cost);
queue<int> Q; Q.push(st), cost[st] = 0, inq[st] = 1;
while (!Q.empty()) {
int u = Q.front(); Q.pop(), inq[u] = 0;
if (u == ed) continue;
for (int i = head[u]; i != -1; i = G[i].next) {
edge &e = G[i];
if (e.w > 0 && cost[e.v] > cost[u] + e.c) {
cost[e.v] = cost[u] + e.c;
pre[e.v] = i;
if (!inq[e.v]) Q.push(e.v), inq[e.v] = 1;
}
}
}
return cost[ed] != 0x3f3f3f3f;
}

int augment(int st, int ed) {
int flow = 0x3f3f3f3f, now = ed;
for (; pre[now] != -1; now = G[pre[now] ^ 1].v) {
flow = min(flow, G[pre[now]].w);
}
for (now = ed; pre[now] != -1; now = G[pre[now] ^ 1].v) {
G[pre[now]].w -= flow, G[pre[now] ^ 1].w += flow;
}
return cost[ed] * flow;
}

int mcmf(int st, int ed) {
int res = 0;
while (spfa(st, ed)) {
res += augment(st, ed);
}
return res;
}

int32_t main() {
int n, a[105], sum = 0, ave;

scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), sum += a[i];
}
ave = sum / n;

for (int i = 1; i <= n; i++) a[i] -= ave;

init();
for (int i = 1; i <= n; i++) {
if (a[i] > 0) addedge(0, i, a[i], 0);
else if (a[i] < 0) addedge(i, n + 1, -a[i], 0);

int nxt = (i == n) ? 1 : (i + 1);
addedge(i, nxt, INF, 1);
addedge(nxt, i, INF, 1);
}
printf("%d\n", mcmf(0, n + 1));
}