负载平衡问题

负载平衡问题"/>

负载平衡问题

本题也是费用流问题，首先求出平均值，每个库存再减去平均值，得到的就是每个应该盈亏的值。建立源点ST和汇点ED，如果得到的值为正就由ST向其连费用为0，流量为其值的边，如果为负，则由其向ED连费用为0，流量为其值绝对值的边。最后每个向两边的点连费用为1，流量为无穷大的边（因为是环，所以注意要特殊处理1和n这两个点），最后跑费用流即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>#define M 1001011
#define INF 0x7fffffff/3
#define ST 2001
#define ED 2002using namespace std;int n,m;
int num=0,ans=0;
int p[M];
int q[4*M];
int cost[M],flag[M],pre[M];
int fx[M];
struct node
{int a;int b;int w;int f;int next;
}str1[M];void add(int x,int y,int z,int fl)
{str1[num].a=x;str1[num].b=y;str1[num].w=z;str1[num].f=fl;str1[num].next=p[x];p[x]=num++;swap(x,y);str1[num].a=x;str1[num].b=y;str1[num].w=-z;str1[num].f=0;str1[num].next=p[x];p[x]=num++;
}bool spfa(int src)
{memset(flag,0,sizeof(flag));for(int i=0;i<=ED;i++)cost[i]=INF;cost[src]=0;flag[src]=1;pre[src]=-1;int l=0,r=0;q[r++]=src;while(l<r){int k=q[l++];flag[k]=0;for(int i=p[k];i!=-1;i=str1[i].next){int v=str1[i].b;if(cost[v]>cost[k]+str1[i].w&&str1[i].f>0){cost[v]=cost[k]+str1[i].w;pre[v]=i;if(!flag[v]){flag[v]=1;q[r++]=v;}}}}if(cost[ED]==INF)return false;return true;
}void start()
{int minx=INF;for(int i=pre[ED];i!=-1;i=pre[str1[i^1].b])minx=min(minx,str1[i].f);for(int i=pre[ED];i!=-1;i=pre[str1[i^1].b]){str1[i].f-=minx;str1[i^1].f+=minx;}ans+=cost[ED]*minx;
}void spfaflow()
{ans=0;while(spfa(ST))start();
}void init()
{scanf("%d",&n);int sum=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);fx[i]=x;sum+=x;}sum=sum/n;for(int i=1;i<=n;i++)fx[i]=fx[i]-sum;
}void start1()
{memset(p,-1,sizeof(p));for(int i=1;i<=n;i++){if(fx[i]>0)add(ST,i,0,fx[i]);if(fx[i]<0)add(i,ED,0,-fx[i]);}for(int i=1;i<=n-1;i++)add(i,i+1,1,INF);for(int i=2;i<=n;i++)add(i,i-1,1,INF);add(n,1,1,INF);add(1,n,1,INF);
}int main()
{freopen("T19.in","r",stdin);freopen("T19.out","w",stdout);init();start1();spfaflow();printf("%d\n",ans);return 0;
}