记录编号	173772	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 负载平衡	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-07-29 20:17:34	内存使用	0.37 MiB

/*最小费用流练习*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=110;
const int inf=0x7fffffff/3;
struct edge{
	int u,v,w,cost,next;
}G[maxn<<2];
int a[maxn],h[maxn],pre[maxn],path[maxn];
int s,t,tot=1,n;
int dist[maxn];// 从起点s到点u的路径长为d
int vis[maxn];
int Q[maxn*100];

void add(int a,int b,int x,int y){
	++tot; G[tot].u=a; G[tot].v=b;
	G[tot].w=x; G[tot].cost=y;
	G[tot].next=h[a]; h[a]=tot;

	++tot; G[tot].u=b; G[tot].v=a;
	G[tot].w=0; G[tot].cost=-y;
	G[tot].next=h[b]; h[b]=tot;
}

bool spfa(int s,int t){
    int u,v;
    queue<int>q;
    for(int i=0;i<=n+2;i++){
        pre[i]=-1;
        vis[i]=0;
        dist[i]=inf;
    }
    //int head=1,tail=1;
    vis[s]=1;
    dist[s]=0;
    q.push(s);
    //Q[1]=s;
    while(!q.empty()){
        u=q.front();
        //u=Q[head];
        //head++;
		//cout<<u<<" ";
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=G[i].next){
            if(G[i].w>0){
                v=G[i].v;
                if(dist[v]>dist[u]+G[i].cost){
                    dist[v]=dist[u]+G[i].cost;
                    pre[v]=u;
                    path[v]=i;
                    /*if (dist[v]<=dist[u]){
						head--;
						Q[head]=v;
                    }*/
                    if(!vis[v]){
                        q.push(v);
						//Q[++tail]=v;
                        vis[v]=1;
                    }
                }
            }
		}
    }
    return dist[t]!=inf;
}

int smallest_cost_flow(){
    int ans=0,flow;
    int flow_sum=0;
    while(spfa(s,t)){
        flow=inf;
        //cout<<dist[t]<<" ";
        for(int i=t;i!=s;i=pre[i]){
            if(G[path[i]].w<flow)
                flow=G[path[i]].w;
		}
        for(int i=t;i!=s;i=pre[i]){
            G[path[i]].w-=flow;
            G[path[i]^1].w+=flow;
		}
		ans+=flow*dist[t];
    }
    return ans;
}

int main()
{
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	scanf("%d",&n);
	s=0; t=n+1;
	int sum=0;
	for (int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	sum=sum/n;
	for (int i=1;i<=n-1;++i){
		add(s,i,a[i],0);
		add(i,t,sum,0);
		add(i,i+1,inf,1);
		add(i+1,i,inf,1);
	}
	add(s,n,a[n],0);
	add(n,t,sum,0);
	add(1,n,inf,1);
	add(n,1,inf,1);
	printf("%d",smallest_cost_flow());
	//system("pause");
}