Description
G公司有 n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
对于给定的 n个环形排列的仓库的库存量，编程计算使 n个仓库的库存数量相同的最少搬运量。
Input
文件的第 1行中有 1个正整数 n（n<=100），表示有 n个仓库。第 2行中有 n个正整数，表示 n个仓库的库存量。
Output
输出最少搬运量
Sample Input
5
17 9 14 16 4
Sample Output
11
题目分析
建超级源点S 汇点T
连边方式：
每个点向它相邻的两个点连一条费用为1 容量为inf的边
S向每个自身库存量大于平均数的点 连一条容量为库存量与平均数的差 费用为0的边
每个自身库存量小于平均数的点向T 连一条容量为平均数与库存量的差 费用为0的边
之后跑最小费用最大流即可
注意 网络流的边数tot初始化为1
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int head[1000],to[100000],val[100000],net[100000],flo[100000];
int n,tot=1;
int path[10000];
void add(int x,int y,int v,int c)
{
net[++tot]=head[x],head[x]=tot,to[tot]=y,flo[tot]=v,val[tot]=c;
net[++tot]=head[y],head[y]=tot,to[tot]=x,flo[tot]=0,val[tot]=-c;
}
int S,T;
int dis[10000],vis[10000];
int spfa()
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
queue<int>q;
vis[S]=1,q.push(S),dis[S]=0;
while(q.size())
{
int nmp=q.front();
vis[nmp]=0;
q.pop();
for(int i=head[nmp];i;i=net[i])
if(flo[i]>0&&dis[to[i]]>dis[nmp]+val[i])
{
dis[to[i]]=dis[nmp]+val[i];
path[to[i]]=i^1;
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
return dis[T]<0x3f3f3f3f;
}
int mincost()
{
int ans=0;
while(spfa())
{
int minflow=0x3f3f3f3f;
for(int i=T;i!=S;i=to[path[i]]) minflow=min(minflow,flo[path[i]^1]);
for(int i=T;i!=S;i=to[path[i]])
{
flo[path[i]]+=minflow;
flo[path[i]^1]-=minflow;
ans+=val[path[i]^1]*minflow;
}
}
return ans;
}
int value[10000];
int mid;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&value[i]),mid+=value[i];
mid=mid/n;
S=0,T=n+1;
for(int i=1;i<=n;i++)
if(value[i]>mid) add(S,i,value[i]-mid,0);
else if(mid>value[i]) add(i,T,mid-value[i],0);
for(int i=1;i<n;i++) add(i,i+1,0x3f3f3f3f,1);
for(int i=n;i>1;i--) add(i,i-1,0x3f3f3f3f,1);
add(n,1,0x3f3f3f3f,1);add(1,n,0x3f3f3f3f,1);
printf("%d",mincost());
return 0;
}
