「网络流24题」负载平衡问题-题解

题目传送门: 「Luogu P4016」负载平衡问题

题目大意

有$n$个环形的仓库,每个仓库存储一定数量的货物
货物可以在相邻仓库之间搬运,最终达到每个仓货物数量一样的效果

求最少搬运次数

题解

看题解说可以用数学方法推导,但是在24题里还是选择用费用流水过

先求出平均数,即目标
然后将每个仓库的货物数减去平均数,得出需要移动的数量

1. 如果大于$0$,则从 源点 向 该仓库 建一条 容量为差值,费用为$0$ 的边(需要转移出,对答案无贡献)
2. 如果小于$0$,则从 该仓库 向 汇点 建一条 容量为差值绝对值,费用为$0$ 的边(吸收这些货物,对答案无贡献)
3. 从 每个仓库 向 相邻两个仓库 建一条 容量为$inf$,费用为$1$ 的边(转移货物的数量无要求,对答案贡献为$1$)

注意建边3.需要考虑环形
求出最小费用最大流,最小费用即为结果

因为费用流大前提是满足最大流,而且此图中源点出发的与流入汇点的边的容量和相等,所以最大流情况下一定会全部流过,即达到仓库货物数量平衡

代码

// 最小费用最大流模板省去了
int num[110], tot;

int main() {
    n = read(); s = 0; t = n + 1;
    for (int i = 1; i <= n; ++i) {
        num[i] = read(); tot += num[i];
    }
    tot /= n;
    for (int i = 1; i <= n; ++i) {
        if (num[i] - tot > 0) add(s, i, num[i] - tot, 0);
        if (num[i] - tot < 0) add(i, t, tot - num[i], 0);
        if (i != 1) {
            add(i, i - 1, inf, 1);
            add(i - 1, i, inf, 1);
        }
    }
    add(1, n, inf, 1);
    add(n, 1, inf, 1);
    ansflow = MinCostMaxFlow(anscost);
    printf("%lld\n", anscost);
    return 0;
}