[文章目录]
Description
G公司有 n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
对于给定的 n个环形排列的仓库的库存量，编程计算使 n个仓库的库存数量相同的最少搬运量。 n<=100
计算每个节点多出的库存或少的库存。多的向s连边，流量为多出的库存，少的向t连边，流量为少的库存。相邻的仓库连边，流量inf，费用为1。（不用考虑是否重边，因为反向弧的流量为0）。跑一边最大流就好了，就相当于将多的库存通过环状的水管全部运向了少的仓库。然后费用就是在环上跑的路程*流量。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,val[110],sum,ans;
int s,t,path[110];
int head[110],to[1000],nxt[1000],f[1000],w[1000],cnt=1;
void add(int x,int y,int z,int k)
{
to[++cnt]=y;
f[cnt]=z;
w[cnt]=k;
nxt[cnt]=head[x];
head[x]=cnt;
to[++cnt]=x;
f[cnt]=0;
w[cnt]=-k;
nxt[cnt]=head[y];
head[y]=cnt;
}
int dis[110];
bool v[110];
bool spfa()
{
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
queue<int>q;
dis[s]=0;q.push(s);v[s]=1;
int x,tmp;
while(!q.empty())
{
x=q.front();q.pop();v[x]=0;tmp=dis[x];
for(int y,i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]>tmp+w[i])
{
dis[y]=tmp+w[i];
path[y]=i^1;
if(!v[y]) q.push(y),v[y]=1;
}
}
return dis[t]<inf;
}
void mincost()
{
while(spfa())
{
int flow=inf;
for(int i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
for(int i=t;i!=s;i=to[path[i]])
{
f[path[i]]+=flow;
f[path[i]^1]-=flow;
ans+=flow*w[path[i]^1];
}
}
}
int main()
{
scanf("%d",&n);
s=n+1,t=n+2;
for(int i=1;i<=n;i++)
scanf("%d",&val[i]),sum+=val[i];
sum/=n;
for(int i=1;i<=n;i++)
{
add(i,i%n+1,inf,1);
add(i,(i+n-2)%n+1,inf,1);
if(val[i]>sum) add(s,i,val[i]-sum,0);
else if(val[i]<sum) add(i,t,sum-val[i],0);
}
mincost();
printf("%d",ans);
return 0;
}