http://codevs.cn/problem/1916/

題解：

我的思考過程： 樣例： 5
17 9 14 16 4

負載平衡問題是一類問題，大意就像題目說的那樣，是個很有用的網絡流模型。《線性規劃與網絡流24題》里有對建模的概述：

首先求出所有倉庫存貨量平均值，設第i個倉庫的盈余量為A[i]，A[i] = 第i個倉庫原有存貨量 - 平均存貨量。建立二分圖，把每個倉庫抽象為兩個節點Xi和Yi。增設附加源S匯T。

//i表示供應，j表示需求。

1、如果A[i]>0，從S向Xi連一條容量為A[i]，費用為0的有向邊。 //可以供應的量

2、如果A[i]<0，從Yi向T連一條容量為-A[i]，費用為0的有向邊。//需求的量

//這就限制了總的流量

3、每個Xi向兩個相鄰頂點j，從Xi到Xj連接一條容量為無窮大，費用為1的有向邊， //搬運過去后，后者（j）立刻滿足供需平衡

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?從Xi到Yj連接一條容量為無窮大，費用為1的有向邊。//暫時搬運過去，在后續操作中滿足供需平衡

求最小費用最大流，最小費用流值就是最少搬運量。

代碼：

總時間耗費: 15ms?
總內存耗費: 256B

#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std;const int maxn = 100 + 100 + 10; const int INF = 1e9 + 7;struct Edge {int from, to, cap, flow, cost; };int n, s, t, A[maxn];vector<Edge> edges; vector<int> G[maxn];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});int m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1); }int d[maxn], p[maxn], a[maxn]; bool inq[maxn];bool BellmanFord(int& cost) {for(int i = s; i <= t; i++) d[i] = INF;memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1; a[s] = INF; p[s] = 0;queue<int> Q;Q.push(s);while(!Q.empty()) {int x = Q.front(); Q.pop();inq[x] = 0;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[e.to] > d[x] + e.cost) {d[e.to] = d[x] + e.cost;p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap-e.flow);if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }}}}if(d[t] == INF) return 0;cost += a[t] * d[t];int x = t;while(x != s) {edges[p[x]].flow += a[t];edges[p[x]^1].flow -= a[t];x = edges[p[x]].from;}return 1; }void MincostMaxflow() {int cost = 0;while(BellmanFord(cost));cout << cost << endl; }int main() {cin >> n;s = 0; t = n + n + 1;int ave = 0;for(int i = 1; i <= n; i++) {cin >> A[i];ave += A[i];}ave /= n;for(int i = 1, j; i <= n; i++) {A[i] -= ave;if(A[i] > 0) AddEdge(s, i, A[i], 0);if(A[i] < 0) AddEdge(i+n, t, -A[i], 0);if((j = i-1) == 0) j = n; AddEdge(i, j, INF, 1); AddEdge(i, j+n, INF, 1);if((j = i+1) > n) j = 1;AddEdge(i, j, INF, 1); AddEdge(i, j+n, INF, 1);}MincostMaxflow();return 0; }

總結

以上是生活随笔為你收集整理的[codevs 1916] 负载平衡问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。