P4015 运输问题

一对一匹配推广为多单位供需

问题

P4015 运输问题
有 $m$ 个仓库和 $n$ 个商店，仓库供给量与商店需求量总和相等。将所有货物运输完，已知每单位从仓库 $i$ 运到商店 $j$ 的费用，分别求最小与最大总运费。

数据规模：$1\le m,n\le100$。

P4014 分配问题 中，每个人只能提供 $1$ 单位“匹配”，每份工作也只能接收 $1$ 单位流。

本题可以视为它的多单位推广，仓库 $i$ 可以提供 $A_{i}$ 单位货物；商店 $j$ 需要接受 $B_{j}$ 单位货物，同一个仓库可以把多单位货物送往同一家或不同商店。

于是还是可以建立 $S\to$ 仓库 $\to$ 商店 $\to T$，区别在于容量不再全是 $1$。

容量与费用

对于仓库 $i$：$S\to i$ 的容量为 $A_i$，表示这个仓库最多能够提供这么多货物。

对于商店 $j$：$j\to T$ 的容量为 $B_j$，表示这个商店最多接收这么多货物。

仓库 $i$ 到商店 $j$ 的容量设置为 $+oo$，单位费用为 $C_{i,j}$。

这里一单位流不再表示“一组匹配”，而是表示“一单位货物”。

如果运输边 $i\to j$ 最终流过 $x$ 单位，就表示从仓库 $i$ 向商店 $j$ 运输了 $x$ 单位货物，并产生 $xC_{i,j}$ 的运输费用。

这和 P4014 分配问题 一样：容量决定一条路线最多能够承担多少资源，费用决定每发送一单位资源需要支付多少代价。

由于总供应量等于总需求量，且任意仓库都可以向任意商店运输，因此网络一定存在流量等于总供应量的完整运输方案。

最小运费直接运行最小费用流即可。最大运费仍然只需要把所有运输边单位费用 $C_{i,j}$ 改成 $-C_{i,j}$，容量结构完全不变，最终答案再取反。

▶

AC 代码

namespace MCMF { /* 模板代码略 */ }
using namespace MCMF;

ll A[105], B[105], C[105][105];

void solve( ) {
    int m = read( ), n = read( );

    vector<int> a( m + 1 );
    vector<int> b( n + 1 );

    int tot = 0;
    for( int i = 1; i <= m; ++ i ) a[i] = ++ tot;
    for( int i = 1; i <= n; ++ i ) b[i] = ++ tot;
    int S = ++ tot, T = ++ tot;

    for( int i = 1; i <= m; ++ i ) A[i] = read( );
    for( int i = 1; i <= n; ++ i ) B[i] = read( );

    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            C[i][j] = read( );
        }
    }
    // =====

    init( tot );
    for( int i = 1; i <= m; ++ i ) {
        add_edge( S, a[i], A[i], 0 );
    }
    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            add_edge( a[i], b[j], inf, C[i][j] );
        }
    }
    for( int i = 1; i <= n; ++ i ) {
        add_edge( b[i], T, B[i], 0 );
    }
    auto [flow1, mincost] = mincost_maxflow( S, T, tot );
    // ===== 

    init( tot );
    for( int i = 1; i <= m; ++ i ) {
        add_edge( S, a[i], A[i], 0 );
    }
    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            add_edge( a[i], b[j], inf, -C[i][j] );
        }
    }
    for( int i = 1; i <= n; ++ i ) {
        add_edge( b[i], T, B[i], 0 );
    }
    auto [flow2, maxcost] = mincost_maxflow( S, T, tot );

    cout << mincost << "\n" << -maxcost << "\n";
}