记录编号	100848	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	（ˇˍˇ） ～耶稣	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-05-08 11:37:24	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

 const int u=210,M=1010,INF=0x3f3f3f3f;
 int ver[M],edge[M],w[M],next[M],head[u],d[u],q[u*3],a[u],last[u];
 int n,tot,ed,st,ans,tv,v[u];
 
 inline int read(void)
 {
 	char ch;
 	while (!isdigit(ch = getchar()));
 	int ret=ch-48;
 	while (isdigit(ch = getchar()))
 	{
 		ret*=10;
 		ret+=ch-48;
 	}
 	return ret;
 }
 
 inline void add(int x, int y, int flow, int cost)
 {
 	ver[++tot]=y;
 	edge[tot]=flow;
 	w[tot]=cost;
 	next[tot]=head[x];
 	head[x]=tot;
 	
 	ver[++tot]=x;
 	edge[tot]=0;
 	w[tot]=-cost;
 	next[tot]=head[y];
 	head[y]=tot;
 }

 bool spfa(void)
 {
 	int i,l,r,x,y;
 	l=r=n+10;
 	tv++;
 	memset(d,INF & 0xff,sizeof(d));
 	d[st]=0;
 	q[l]=st;//push_front
 	while (l <= r)
 	{
 		x=q[l]; l++;
 		v[x]=0;//pop
 		for (i=head[x]; i; i=next[i])
 		{
 			y=ver[i];
 			if (edge[i]>0 && d[y]>d[x]+w[i])
 			{
 				d[y]=d[x]+w[i];
 				if (v[y] != tv)
 				 if (d[y]<=d[x])
 				 {
 					q[--l]=y;
 					v[y]=tv;
 				 }
 				 else{
 				 	q[++r]=y;
 				 	v[y]=tv;
 				 }
 			}
 		}
 		tv++;
 	}
 	if (d[ed] != d[ed+1]) return true;
 	else return false;
 }
 
 int dfs(int x, int f)
 {
 	if (x == ed) return f;
 	int shit,y,j,k;
 	k=0;
 	v[x]=tv;
 	for (j=head[x]; j; j=next[j])
 	{
 		y=ver[j];
 		if (f>0 && v[y]!=tv && edge[j]>0 && d[y]==d[x]+w[j])
 		{
 			shit=dfs(y,min(f,edge[j]));
 			f-=shit;  k+=shit;
 			edge[j]-=shit;
 			edge[j^1]+=shit;
 			ans+=shit*w[j];
 		}
 	}
 	v[x]=0;
 	if (k == 0) d[x]=-INF;
 	return k;
 }
 
 void orz_dinic(void)
 {
 	tv=0;
 	memset(v,0,sizeof(v));
 	while (spfa())
 		do{
 			++tv;
 		}while (dfs(st,INF));
 }
 
int main()
{
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	
	n=read();
	int sum=0;
	tot=1;
	st=0; ed=n+1;
	memset(head,0,sizeof(head));
	for (int i=1; i<=n; i++)
	{
		a[i]=read();
		sum+=a[i];
	}
	sum/=n;
	for (int i=1; i<n; i++)
	{
		add(st,i,a[i],0);
		add(i,ed,sum,0);
		add(i,i+1,INF,1);
		add(i+1,i,INF,1);
	}	
	add(st,n,a[n],0);
	add(n,ed,sum,0);
	add(1,n,INF,1);
	add(n,1,INF,1);
	memset(last,0,sizeof(last));
	ans=0;
	orz_dinic();
	printf("%d\n",ans);	
	return 0;
}