网络流24题之十九 负载平衡问题

G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。
«编程任务：
对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少搬运量。

第1 行中有1 个正整数n（n<=100），表示有n个仓库。第2 行中有n个正整数，表示n个仓库的库存量。

将计算出的最少搬运量输出

5
17 9 14 16 4

11

模型

转化为供求平衡问题，用最小费用最大流解决。

实现

首先求出所有仓库存货量平均值，设第i个仓库的盈余量为A[i]，A[i] = 第i个仓库原有存货量 – 平均存货量。建立二分图，把每个仓库抽象为两个节点Xi和Yi。增设附加源S汇T。

1、如果A[i]>0，从S向Xi连一条容量为A[i]，费用为0的有向边。
2、如果A[i]<0，从Yi向T连一条容量为-A[i]，费用为0的有向边。
3、每个Xi向两个相邻顶点j，从Xi到Xj连接一条容量为无穷大，费用为1的有向边，从Xi到Yj连接一条容量为无穷大，费用为1的有向边。

求最小费用最大流，最小费用流值就是最少搬运量。

分析

计算出每个仓库的盈余后，可以把问题转化为供求问题。建立供求网络，把二分图X集合中所有节点看做供应节点，Y集合所有节点看做需求节点，在能一次搬运满足供需的Xi和Yj之间连接一条费用为1的有向边，表示搬运一个单位货物费用为1。另外还要在Xi与相邻的Xj之间连接边，表示货物可以暂时搬运过去，不立即满足需求，费用也为1。最大流满足了所有的盈余和亏损供求平衡，最小费用就是最少搬运量。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 20010
#define N 500
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool spfa(int S,int T)
{
    memset(dis,0x33,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]<INF;
}
Pair mfmc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(spfa(S,T))
    {
        flow=INF;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
//1、如果A[i]>0，从S向Xi连一条容量为A[i]，费用为0的有向边。
//2、如果A[i]<0，从Yi向T连一条容量为-A[i]，费用为0的有向边。
//3、每个Xi向两个相邻顶点j，从Xi到Xj连接一条容量为无穷大，费用为1的有向边，
////从Xi到Yj连接一条容量为无穷大，费用为1的有向边。
main()
{
    int m,val[N],sum=0,j;
    scanf("%d",&n);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    int S=0,T=n+n+1;
    for (int i=1;i<=n;i++)
        scanf("%d",&val[i]),sum+=val[i];
    int avg=sum/n;
    for (int i=1;i<=n;i++)
    {
        val[i]-=avg;
        if (val[i]>0)
            add_edge(S,i,val[i],0);
        else if (val[i]<0)
            add_edge(i+n,T,-val[i],0);
        if ((j=i+1)>n) j=1;
        add_edge(i,j,INF,1);
        add_edge(i,j+n,INF,1);
        if ((j=i-1)<1) j=n;
        add_edge(i,j,INF,1);
        add_edge(i,j+n,INF,1);
    }
    Pair ans=mfmc(S,T);
    printf("%d\n",ans.second);
}