P4014 分配问题

给匹配边加上单位费用

问题

P4014 分配问题
将 $n$ 个人与 $n$ 件工作一一分配。第 $i$ 个人完成第 $j$ 件工作的效益为 $c_{i,j}$，分别求总效益最小与最大的可行方案。

数据规模：$1\le n\le50$，$0\le c_{i,j}\le100$。

在 P2756 飞行员配对方案问题 中，我们已经把二分图匹配写成单位容量流网络：$S\to$ 人 $\to$ 工作 $\to T$。

容量负责表达“每个人只能选择一份工作，每份工作也只能被一个人选择”。本题的结构完全没有变化，只是不同的匹配边现在拥有不同的效益。

于是最自然的推广就是：除了容量，再给每条边增加一个单位费用。

那么问题来了，费用挂在哪里？

源点到人的边、工作到汇点的边仍然只负责限制使用次数，因此费用都设为 $0$。而真正决定“第 $i$ 个人做第 $j$ 份工作”的，是中间的选择边 $i\to j$。所以令：

• $S\to i$，容量 $1$，费用 $0$；
• $i\to j$，容量 $1$，费用 $c_{i,j}$；
• $j\to T$，容量 $1$，费用 $0$。

于是每发送一单位完整流，就表示确定一组“人—工作”的分配，同时产生对应的 $c_{i,j}$ 单位费用。

这里就可以体现 容量 和 费用的不同职责了：容量回答 “这个选择最多能发生几次”，而费用回答 “这个选择一旦发生，要贡献多少代价”。

为什么一定要送满 $n$ 单位流呢？如果只要求费用尽量小，而不要求完成所有分配，那么流量为 $0$、费用为 $0$ 就可能成为答案。

但原题要求 $n$ 个人和 $n$ 份工作一一对应，因此最终必须形成一个完美匹配，也就是总共发送 $n$ 单位流。

所以本题真正要求的：是在所有流量恰好为 $n$ 的可行流中，使总费用最少。

而由于这张图是完全二分图，最大流一定能到达 $n$，因此求这种 最小费用最大流 时，最终会在所有完整分配中找到费用最小的一种。

残量网络

普通最大流的反向边表示“撤销之前送出的流”。费用流中除了撤销流量，还必须撤销之前产生的费用。

因此若正向边 $u\to v$ 的费用为 $w$，那么对应反向边 $v\to u$ 的费用就是 $-w$。如果之前沿 $u\to v$ 发送了一单位流，总费用增加 $w$；以后若沿反向边撤销这一单位流，总费用就应该减少 $w$。

所以费用流中的残量网络不仅记录“还能怎样调整流量”，还记录了：怎样调整当前方案，以及这种调整会使总费用发生多少变化。

每次寻找最短费用增广路时，路径中既可以包含尚未使用的正向选择，也可以包含撤销已有选择的反向边，因此算法并不是简单地贪心选择当前最便宜的未使用边。

因此在费用流中，每次需要在当前残量网络中寻找一条费用最短的增广路。可以使用 SPFA，或使用势能维护后配合 Dijkstra 完成这一过程。

最大费用

要求最大总效益时，容量结构完全不用改变。把所有选择边费用 $c_{i,j}$ 改成 $-c_{i,j}$，那么原来的 “效益最大” 就变成 “负效益之和最小”。再运行一次最小费用流，最后把答案取反即可。

▶

P4014 费用流

struct Edge { int v; ll c, w; };
vector<Edge> edge;
vector< vector<int> > adj;

void init( int N, int M = 0 ) {
    edge.clear( );
    if( M ) edge.reserve( M << 1 );
    adj.assign( N + 1, { } );
}

// 加一条容量为 c、单位费用为 w 的有向边 u -> v。
void add_edge( int u, int v, ll c, ll w ) {
    if( u == v ) return;
    adj[u].push_back( edge.size( ) );
    edge.push_back({ v, c, w });
    adj[v].push_back( edge.size( ) );
    edge.push_back({ u, 0, -w });
}

ll mxf[maxn];
ll dis[maxn];
int pre[maxn];
bool inq[maxn];

// 在残量网络中寻找一条最短费用增广路。
bool spfa( int S, int T, int N ) {
    for( int i = 0; i <= N; ++ i ) {
        dis[i] = inf, mxf[i] = 0;
        pre[i] = -1, inq[i] = false;
    }
    queue<int> q; q.push( S );
    dis[S] = 0, mxf[S] = inf, inq[S] = true;
    while( !q.empty( ) ) {
        int u = q.front( ); q.pop( );
        inq[u] = false;
        for( int id : adj[u] ) {
            auto [v, c, w] = edge[id];
            if( c == 0 || dis[u] + w >= dis[v] ) continue;
            dis[v] = dis[u] + w;
            mxf[v] = min( mxf[u], c );
            pre[v] = id;
            if( !inq[v] ) inq[v] = true, q.push( v );
        }
    }
    return pre[T] != -1;
}

// 返回 {最大流量, 对应的最小费用}。
pair<ll, ll> mincost_maxflow( int S, int T, int N, ll limit = inf ) {
    ll flow = 0, cost = 0;
    while( flow < limit && spfa( S, T, N ) ) {
        ll f = min( mxf[T], limit - flow );
        flow += f;
        cost += f * dis[T];
        for( int v = T; v != S; ) {
            int id = pre[v];
            edge[id].c -= f;
            edge[id ^ 1].c += f;
            v = edge[id ^ 1].v;
        }
    }
    return { flow, cost };
}

ll a[55][55];

void solve( ) {
    int n = read( );
    int S = 0, T = 2 * n + 1;

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

    init( T );
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            add_edge( i, n + j, 1, a[i][j] );
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        add_edge( S, i, 1, 0 );
        add_edge( n + i, T, 1, 0 );
    }

    auto [flow1, mincost] = mincost_maxflow( S, T, T, n );

    init( T );
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            add_edge( i, n + j, 1, -a[i][j] );
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        add_edge( S, i, 1, 0 );
        add_edge( n + i, T, 1, 0 );
    }

    auto [flow2, maxcost] = mincost_maxflow( S, T, T );

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