「题解」负载平衡问题

2019.4第一道题，也是第二道wll24题，希望能rp++……

一 题目

原题链接

描述

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

输入

文件的第 1 行中有 1 个正整数 n，表示有 n 个仓库。
第 2 行中有 n 个正整数，表示 n 个仓库的库存量。

输出

输出最少搬运量。

---

二 题解

wll24题中蓝色的题目2/3，rp++。

本题有数学解法！但是我太菜了。

既然是最少搬运量，那么肯定跟费用流有关。关键就是这个怎么均分负载的问题了。

可以计算库存量（设它为$a_i$）的平均数$\overline a$。如果有解，那么最后每个仓库的库存量都一定会是$\overline a$。可以把仓库分成两类：

1. $a_i > \overline a$ 的仓库$i$，记为图$L$。
2. $a_i < \overline a$ 的仓库$i$，记为图$R$。

$a_i = \overline a$的仓库不会影响答案，所以放在哪一类里面都行。

很明显，$L$中节点的点权需要转移到$R$中节点去。把这个点权变成边权，那么新建总源$s$和总汇$t$，连边$s\to L$，$L \rightleftarrows R$与$R\to t$。
$s\to L$边上的流量限制为$L$中节点点权超出$\overline a$的部分，即$a_i - \overline a$。
$R\to t$边上的流量限制为$R$中节点点权不足$\overline a$的部分，即$\overline a- a_i$。
图上所有相邻节点互相连双向边，边上没有流量限制，因为可以无限转移。不过转移的费用就是$1$。

这样，当增广一条路时，$s\to L$的边流量增大，$R\to t$的边流量也增大，其实意味着$L,R$中点的点权会更接近于平均值$\overline a$。当网络流达到最大时，也就是说所有不等于平均值的点权都已经被增广到平均值大小，也就达到了负载平衡（前提是保证有解！）。

然后只需要处理一下环。

代码：

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

const int CP=101*10;
const int CE=CP*CP;

const int INF=0x3f3f2f3f;

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

class fs{
  public:
      int from,to,nxt,flow,cap,cost;
      void init(int f,int t,int n,int w,int c,int s)
      {from=f; to=t; nxt=n; flow=w; cap=c; cost=s;}
}E[CE];
int hd[CP],ecnt=1;
void _add(int x,int y,int c,int w){
    E[++ecnt].init(x,y,hd[x],0,c,w);
    hd[x] = ecnt;
}
void add(int x,int y,int c,int w){
    _add(x,y,c,w);
    _add(y,x,0,-w); //反向边 
}

//v define
int n,_a,s,t;
int a[CP];

//mcmf
int maxflow=0,mincost=0;
int d[CP],rst[CP],prv[CP];
bool ins[CP];

bool Augment(int _s,int _t){
    memset(d,0x3f,sizeof(d));
    memset(ins,false,sizeof(ins));
    memset(prv,0,sizeof(prv));
    memset(rst,0x3f,sizeof(rst));
    
    queue<int>Q; Q.push(_s);
    d[_s] = 0; ins[_s] = true;
    
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop(); ins[u] = false;
        
        for(int k=hd[u]; k; k=E[k].nxt)
        {
            fs e=E[k];
            if(e.cap-e.flow>0 && d[e.to]>d[u]+e.cost){
                d[e.to] = d[u]+e.cost;
                prv[e.to] = k;
                rst[e.to] = min(rst[u], e.cap-e.flow);
                if(!ins[e.to]) Q.push(e.to),ins[e.to] = true;
            }
        }
    }
    
    return d[_t] < INF;
}
void update(int _s,int _t,int r){
    int pos=_t;
    while(pos != _s){
        E[prv[pos]].flow += r;
        E[prv[pos]^1].flow -= r;
        pos = E[prv[pos]].from;
    }
}
void mcmf(int _s,int _t){
    while(Augment(_s, _t)){
        maxflow += rst[_t];
        mincost += d[_t]*rst[_t];
        update(_s,_t, rst[_t]);
    }
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),_a+=a[i];
    _a /= n;
    
    s=n+1; t=n+2;
    
    for(int i=1;i<=n;i++) //connect s/t with i
        if(a[i] > _a) add(s,i, a[i]-_a, 0);
            else add(i,t, _a-a[i], 0);
    for(int i=2;i<n;i++){ //connect between nodes
        add(i,i+1, INF, 1);
        add(i,i-1, INF, 1);
    }
    //circle
    add(1,n, INF, 1); add(1,2, INF, 1);
    add(n,1, INF, 1); add(n,n-1, INF, 1);
    
    mcmf(s,t);
    
    printf("%d",mincost);
    
    return 0;
}