记录编号	157626	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	vampire	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2015-04-09 17:31:14	内存使用	4.51 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 210000000LL
struct S{
	int st,en,va,cost;
}aa[20000];
int n,a[110],ave=0,l[1000000],dis[210],pre[210],point[210]={0},next[20000]={0},tot=1;
bool f[210];
void add(int i,int j,int x,int y){
	tot+=1;next[tot]=point[i];point[i]=tot;
	aa[tot].st=i;aa[tot].en=j;aa[tot].va=x;aa[tot].cost=y;
	tot+=1;next[tot]=point[j];point[j]=tot;
	aa[tot].st=j;aa[tot].en=i;aa[tot].va=0;aa[tot].cost=-y;
}
int SPFA(int x,int y)
{
	memset(f,1,sizeof(f));
	memset(dis,127/3,sizeof(dis));
	memset(pre,0,sizeof(pre));
	int i,j,u,h=1,t=1;
	dis[x]=0;l[h]=x,pre[x]=x;
	while(h<=t){
		u=l[h];f[u]=true;
		for(i=point[u];i;i=next[i]){
			if(aa[i].va>0&&dis[aa[i].en]>dis[u]+aa[i].cost){
				dis[aa[i].en]=dis[u]+aa[i].cost;
				pre[aa[i].en]=i;
				if(f[aa[i].en]){
					t+=1;
					f[aa[i].en]=false;
					l[t]=aa[i].en;
				}
			}
		}
		h+=1;
	}
	return dis[y]>100000000?0:dis[y];
} 
int ISAP(int x,int y)
{
	int i,minn=inf;
	for(i=y;i!=x;i=aa[pre[i]].st){
		minn=min(minn,aa[pre[i]].va);
	}
	for(i=y;i!=x;i=aa[pre[i]].st){
		aa[pre[i]].va-=minn;
		aa[pre[i]^1].va+=minn;
	}
	//cout<<minn<<endl;
	return minn;
}
int main()
{
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ave+=a[i];
	}
	ave/=n;
	for(i=1;i<=n;++i){
		if(a[i]>ave) add(1,i+1,a[i]-ave,0);
		if(a[i]<ave) add(n+i+1,n*2+2,ave-a[i],0);
	}
	for(i=1;i<=n;++i){
		if(i==1||i==n){
		    if(i==1){
		    	add(2,3,inf,1); add(2,n+1,inf,1);
		    	add(2,n+3,inf,1); add(2,n*2+1,inf,1);
			}
			else{
				add(n+1,2,inf,1); add(n+1,n,inf,1);
				add(n+1,n+2,inf,1); add(n+1,n*2,inf,1);
				}
		}
		else{
			add(i+1,i+2,inf,1); add(i+1,i,inf,1);
			add(i+1,i+2+n,inf,1); add(i+1,i+n,inf,1);
		}
	}
	int minn=1,ans=0;
	while(minn){
		minn=SPFA(1,n*2+2);
		//cout<<minn<<' ';
		if(minn) ans+=minn*ISAP(1,n*2+2);
	}
	printf("%d\n",ans);
}