题目描述
GG 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

输入格式
文件的第 1 行中有 1 个正整数 n，表示有 n 个仓库。

第 2 行中有 n 个正整数，表示 n 个仓库的库存量。

输出格式
输出最少搬运量。

输入输出样例
输入
5
17 9 14 16 4

输出
11

说明/提示
1≤n≤100

极其***的我（不拆点要死？）

看到这道题，不难想到，要么直接贪心，要么费用流。

既然是网络流24题，给出费用流做法：

首先建立超级源点S，与超级汇点T,让S到每个仓库连边，费用为0，流量为仓库的库存量。让仓库到T连边，费用为0，流量为所有库存的平均值。（这样可以保证一定是最大流，并且最后库存都一样）。然后让相邻的仓库之间连线，流量为正无穷，费用为1。（注意1和n特判，因为形成了一个环）。

然后可得：最大流保证了库存一样，最小费用保证了最小的搬运量，直接跑一遍费用流即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=410;
const int inf=0x3f3f3f3f;
int n,s,t,a[N],sum,d[N];
int head[N],nex[N<<2],to[N<<2],flow[N<<2],w[N<<2],tot=1;
struct node{
	int v,e;
}p[N];
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,inf,sizeof d);	d[s]=0;	queue<int>	q;	q.push(s);
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				p[to[i]].v=u;	p[to[i]].e=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=p[i].v)	mi=min(mi,flow[p[i].e]);
		for(int i=t;i!=s;i=p[i].v){
			flow[p[i].e]-=mi;	flow[p[i].e^1]+=mi;
		}	 
		res+=d[t]*mi;
	} 
	return res;
}
signed main(){
	cin>>n;	s=0;	t=n+1;
	for(int i=1;i<=n;i++)	cin>>a[i],sum+=a[i];	sum/=n;
	for(int i=1;i<=n;i++){
		add(s,i,a[i],0);	add(i,t,sum,0);
	}
	for(int i=1;i<=n;i++){
		if(i==1)	add(i,i+1,inf,1),add(i,n,inf,1);
		else if(i==n)	add(i,1,inf,1),add(i,i-1,inf,1);
		else	add(i,i+1,inf,1),add(i,i-1,inf,1);
	}
	cout<<EK()<<endl;
	return 0;
}