活動 - AcWing

G?公司有?n?個沿鐵路運輸線環形排列的倉庫，每個倉庫存儲的貨物數量不等。

如何用最少搬運量可以使?n?個倉庫的庫存數量相同。

搬運貨物時，只能在相鄰的倉庫之間搬運。

數據保證一定有解。

輸入格式

第?1?行中有?1?個正整數?n，表示有?n?個倉庫。

第?2?行中有?n?個正整數，表示?n?個倉庫的庫存量。

輸出格式

輸出最少搬運量。

數據范圍

1≤n≤100
每個倉庫的庫存量不超過?100

輸入樣例：

5
17 9 14 16 4

輸出樣例：

11

解析：?

我們可以計算出最終每個倉庫的貨物數量 x，設第 i?個倉庫的貨物數量是 ai，那么所有貨物一定會分成兩類，一類是 ai>x，即一定會從這些倉庫中流出貨物，另一類是 ai<x，即一定會有貨物流入這些倉庫。

因此我們可以根據這兩類，將所有 ai>x?的倉庫作為左部節點，所有 ai<x?的倉庫作為右部節點。從源點向所有左部節點連邊，容量就是左部節點最開始多出來的貨物，即 ai?x，費用就是 0，因為最開始貨物就在左部節點中。從所有右部節點向匯點連邊，容量就是右部節點缺少的貨物，即 x?ai，費用也是 0，因為最終貨物到右部節點就停止了。然后從每個倉庫向相鄰兩個倉庫連邊，容量是 +∞，費用是 1，表示一次搬運量。

然后還需要證明對應關系，對于任意一個原問題的情況，從源點流進倉庫的流量等于流出的流量（根據上述新圖的定義），滿足流量守恒；又因為根據上述新圖的定義，易知邊一定滿足容量限制，所以原問題的方案對應一個最大流。同時，更具上述的建的新圖，易知流量產生的費用對應一個問題的方案。因此，原問題和新圖的最大流是一一對應的，且數值上相等。

并且可以發現原問題的搬運量就對應的流網絡的可行流的費用，因此最小搬運量就對應了最小費用最大流，用 EK 算法來求即可

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100 + 10, M = (100*2+100) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M],w[M], ne[M],idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int p[N];void add(int a, int b, int c,int d) {e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}bool spfa() {int hh = 0, tt = 1;memset(d, 0x3f, sizeof d);memset(incf, 0, sizeof incf);q[0] = S, d[S] = 0, incf[S] = 0x3f;while (hh != tt) {int t = q[hh++];if (hh == N)hh = 0;st[t] = 0;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (f[i] && d[j] > d[t] + w[i]) {d[j] = d[t] + w[i];pre[j] = i;incf[j] = min(incf[t], f[i]);if (!st[j]) {q[tt++] = j;if (tt == N)tt = 0;st[j] = 1;}}}}return incf[T] > 0;
}int EK() {int cost = 0;while (spfa()) {int t = incf[T];cost += t * d[T];for (int i = T; i != S; i = e[pre[i] ^ 1]) {f[pre[i]] -= t;f[pre[i] ^ 1] += t;}}return cost;
}int main() {cin >> n;memset(h, -1, sizeof h);S = 0, T = n + 1;int tot = 0;for (int i = 1,a; i <= n; i++) {scanf("%d", &p[i]);tot += p[i];add(i, i < n ? i + 1 : 1, INF, 1);add(i, i > 1 ? i - 1 : n, INF, 1);}tot /= n;for (int i = 1; i <= n; i++) {if (p[i] > tot)add(S, i, p[i] - tot, 0);else if(tot>p[i])add(i, T, tot - p[i], 0);}printf("%d\n", EK());return 0;
}