「网络流24题」运输问题-题解

题目传送门: 「Luogu P4015」运输问题

题目大意

$m$个仓库,$n$个商店,每个仓库有$a_i$个货物,每个商店需要$b_i$个货物
需要从仓库运输货物到商店中,且第$i$个仓库运输到第$j$个商店费用为$c_{i,j}$

求最小费用和最大费用

题解

和P4015 分配问题一样
将所有仓库和所有商店各分为一个点集

1. 从 源点 向 每个仓库 建一条 容量为货物个数$a_i$,费用为$0$ 的边(有$a_i$个货物需要运出,且对答案无贡献)
2. 从 每个商店 向 汇点 建一条 容量为货物个数$b_i$,费用为$0$ 的边(需要$b_i$个货物,且对答案无贡献)
3. 从 每个仓库 向 每个商店 建一条 容量为$inf$,费用为对应费用 的边(每个仓库可以运出的最多货物不限制,且对答案工作为对应费用)

求出最小费用最大流和最大费用最大流即可

由于费用流的大前提是流量最大,所以一定满足题目中要求的供需平衡即$\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$

代码

// 费用流模板省略,在P4015题解那里有
// 代码里为了方便把mn调换了
int input1[110], input2[110], input3[110][110];

int main() {
    n = read(); m = read();
    s = 0; t = n + m + 1;

    for (int i = 1; i <= n; ++i) {
        int c = read(); input1[i] = c;
        add(s, i, c, 0);
    }
    for (int i = 1; i <= m; ++i) {
        int c = read(); input2[i] = c;
        add(i + n, t, c, 0);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int c = read(); input3[i][j] = c;
            add(i, j + n, inf, c);
        }
    }
    ansflow = MinCostMaxFlow(anscost);
    printf("%lld\n", anscost);

    edges.clear();
    for (int i = 0; i < maxn; ++i) G[i].clear();
    for (int i = 1; i <= n; ++i) add(s, i, input1[i], 0);
    for (int i = 1; i <= m; ++i) add(i + n, t, input2[i], 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            add(i, j + n, inf, input3[i][j]);
        }
    }
    ansflow = MaxCostMaxFlow(anscost);
    printf("%lld\n", anscost);

    return 0;
}