负载运输平衡问题

解题思路

每个仓库最开始都有一定数量的货物，每个仓库可以向相邻两个仓库搬运货物，要求用最少的搬运量是所有仓库的货物数量相等。

我们可以计算出最终每个仓库的货物数量 $x$，设第 $i$ 个仓库的货物数量是 $a_i$，那么所有货物一定会分成两类，一类是 $a_i > x$，即一定会从这些仓库中流出货物，另一类是 $a_i < x$，即一定会有货物流入这些仓库。

因此我们可以根据这两类，将所有 $a_i > x$ 的仓库作为左部节点，所有 $a_i < x$ 的仓库作为右部节点。从源点向所有左部节点连边，容量就是左部节点最开始多出来的货物，即 $a_i - x$，费用就是 $0$，因为最开始货物就在左部节点中。从所有右部节点向汇点连边，容量就是右部节点缺少的货物，即 $x - a_i$，费用也是 $0$，因为最终货物到右部节点就停止了。然后从每个仓库向相邻两个仓库连边，容量是 $+\infty$，费用是 $1$，表示一次搬运量。

然后还需要证明对应关系，对于任意一个原问题的情况，对应的将流网络中的边设置上对应的流量，即可得到一个整数型满流。对于任意一个整数型满流，我们看一下中间仓库之间的边的流量是多少，等价于相应的仓库向相邻两边流了多少货物，这样就能得到一个操作方案上。由此证明了一一对应的关系。

并且可以发现原问题的搬运量就对应的流网络的可行流的费用，因此最小搬运量就对应了最小费用最大流，用 EK 算法来求即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 610, INF = 0x3f3f3f3f;

int n, m, S, T;
int s[N]; //记录每个仓库最开始的货物数量
int h[N], e[M], f[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], pre[N], incf[N]; //EK 算法需要的数组
bool st[N]; //spfa 需要的判重数组

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

bool spfa() //判断是否存在最短增广路
{
    int hh = 0, tt = 1;
    q[0] = S;

    memset(d, 0x3f, sizeof d);
    d[S] = 0;

    memset(incf, 0, sizeof incf);
    incf[S] = INF;

    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(incf[t], f[i]);

                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;

                    st[j] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

int EK() //EK 算法求最小费用最大流
{
    int cost = 0;
    while(spfa())
    {
        int t = incf[T];
        cost += t * d[T];

        for(int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = n + 1; //源点、汇点
    int sum = 0; //记录总货物
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        sum += s[i];

        //从每个仓库向相邻两个仓库连边，容量是 INF，费用是 1
        add(i, i < n ? i + 1 : 1, INF, 1);
        add(i, i > 1 ? i - 1 : n, INF, 1);
    }

    int avg = sum / n; //记录每个仓库最终的货物数量
    for(int i = 1; i <= n; i++)
        if(avg < s[i]) //如果该仓库货物过多，作为左部节点
            add(S, i, s[i] - avg, 0); //从源点向左部节点连一条边，容量是 s[i] - avg，费用是 0
        else //如果该仓库货物过少，作为右部节点
            add(i, T, avg - s[i], 0); //从右部节点向汇点连一条边，容量是 avg - s[i]，费用是 0

    printf("%d\n", EK()); //最小费用最大流

    return 0;
}