【网络流24题】负载平衡问题（费用流）

【网络流24题】负载平衡问题

题目描述 Description

G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最
少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
«编程任务：
对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少
搬运量。

输入描述 Input Description

第1 行中有1 个正整数n（n<=100），表示有n
个仓库。第2 行中有n个正整数，表示n个仓库的库存量。

输出描述 Output Description

将计算出的最少搬运量输出

样例输入 Sample Input

5
17 9 14 16 4

样例输出 Sample Output

11

题意好理解，十分简单，就是S向Xi连一条ai的边，花费为0，Xj向T连一条bal（代表平均）边，费用为0

然后Xi相Xi+1，Xi-1连一条流量无限，费用为1的边。

跑费用流即可。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<iostream>
 6 #include<queue>
 7 
 8 #define N 2007
 9 #define M 1000007
10 #define inf 1000000007
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 int n,S,T;
21 int cnt=1,head[N],rea[M],val[M],cost[M],next[M];
22 int dis[N],flag[N],a[N];
23 struct Node
24 {
25     int e,fa;
26     void init(){e=fa=-1;}
27 }pre[N];
28 
29 void add(int u,int v,int fee,int pay)
30 {
31     next[++cnt]=head[u];
32     head[u]=cnt;
33     rea[cnt]=v;
34     val[cnt]=fee;
35     cost[cnt]=pay;
36 }
37 bool Spfa()
38 {
39     for (int i=S;i<=T;i++)
40         dis[i]=inf,flag[i]=0,pre[i].init();
41     queue<int>q;q.push(S);
42     dis[S]=0,flag[S]=1;
43     while(!q.empty())
44     {
45         int u=q.front();q.pop();
46         for (int i=head[u];i!=-1;i=next[i])
47         {
48             int v=rea[i],fee=cost[i];
49             if ((dis[v]>dis[u]+fee)&&val[i]>0)
50             {
51                 dis[v]=dis[u]+fee;
52                 pre[v].fa=u,pre[v].e=i;
53                 if (!flag[v])
54                 {
55                     flag[v]=1;
56                     q.push(v);
57                 }
58             }
59         }
60         flag[u]=0;
61     }
62     if (dis[T]==inf)return 0;
63     else return 1;
64 }
65 int mfmc()
66 {
67     int flow=0,res=0;
68     while(Spfa())
69     {
70         int x=inf;
71         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
72         {
73             int e=pre[i].e;
74             x=min(x,val[e]);
75         }
76         flow+=x,res+=dis[T]*x;
77         for (int i=T;pre[i].fa!=-1;i=pre[i].fa)
78         {
79             int e=pre[i].e;
80             val[e]-=x,val[e^1]+=x;
81         }
82     }
83     return res;
84 }
85 int main()
86 {
87     memset(head,-1,sizeof(head));
88     n=read();int pal=0;
89     for (int i=1;i<=n;i++)a[i]=read(),pal+=a[i]; pal/=n;
90     S=0,T=2*n+1;
91     for (int i=1;i<=n;i++)add(S,i,a[i],0),add(i,S,0,0);
92     for (int i=1;i<=n;i++)add(i+n,T,pal,0),add(T,i+n,0,0);
93     for (int i=1;i<=n;i++)add(i,i+n,inf,0),add(i+n,i,0,0);
94     for (int i=2;i<=n-1;i++)add(i,i-1,inf,1),add(i-1,i,0,-1),add(i,i+1,inf,1),add(i+1,i,0,-1);
95     add(1,n,inf,1),add(n,1,0,-1),add(1,2,inf,1),add(2,1,0,-1);
96     add(n,n-1,inf,1),add(n-1,n,0,-1),add(n,1,inf,1),add(1,n,0,-1);
97     printf("%d
",mfmc());
98 }