费用流

• OI Wiki: https://oi-wiki.org/graph/flow/min-cost/

题目	难度
1947. 最大兼容性评分和	困难

定义

给定一个网络 G = (V, E)，每条边 (x, y) 除了有容量限制 c(x, y)，还有一个给定的“单位费用” w(x, y)。当边 (x, y) 的流量为 f(x, y) 时，就要花费 f(x, y) * w(x, y)。该网络中总花费最小的最大流被称为“最小费用最大流”，总花费最大的最大流被称为“最大费用最大流”，二者合称为“费用流”模型。注意，费用流的前提是最大流，然后才考虑费用的最值。

类似于“二分图最大匹配”与最大流关系，“二分图带权最大匹配”可直接用最大费用最大流求解，每条边的权值就是它的单位费用。

《算法竞赛进阶指南》

1947. 最大兼容性评分和

class Solution {
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        // m 名学生和 m 名导师，n 个问题
        int m = students.length;
        int n = students[0].length;

        // score[i][j] 表示第 i 个学生与第 j 个老师的 兼容性评分
        int[][] score = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    if (students[i][k] == mentors[j][k]) {
                        score[i][j] += 1;
                    }
                }
            }
        }

        // [1,m] [m+1, 2m] 2m+1 2m+2
        S = 2 * m + 1;
        T = 2 * m + 2;
        tot = 1;
        for (int i = 1; i <= m; i++) {
            add(S, i, 1, 0);
            add(i + m, T, 1, 0);
            for (int j = 1; j <= m; j++) {
                add(i, j + m, 1, score[i - 1][j - 1]);
            }
        }
        while (spfa()) update();
        return (int) ans;
    }

    int N = 20, M = 200;
    int[] ver = new int[M], he = new int[N], ne = new int[M], pre = new int[N], vis = new int[N];
    long[] ed = new long[M], cost = new long[M], dis = new long[N], incf = new long[N];
    int tot, S, T;
    long INF = (long) 1e18;
    long maxflow, ans;

    void add(int x, int y, long z, int c) {
        // 正向边，初始容量 z，单位费用 c
        ver[++tot] = y;
        ed[tot] = z;
        cost[tot] = c;
        ne[tot] = he[x];
        he[x] = tot;
        // 反向边，初始容量 0，单位费用 -c，与正向边 成对存储
        ver[++tot] = x;
        ed[tot] = 0;
        cost[tot] = -c;
        ne[tot] = he[y];
        he[y] = tot;
    }

    boolean spfa() {
        Queue<Integer> q = new ArrayDeque<>();
        Arrays.fill(dis, -INF);
        q.add(S);
        dis[S] = 0;
        vis[S] = 1; // SPFA 求最长路
        incf[S] = INF; // 增广路上各边的最小剩余容量
        while (!q.isEmpty()) {
            int x = q.remove();
            vis[x] = 0;

            for (int i = he[x]; i != 0; i = ne[i]) {
                int y = ver[i];
                if (ed[i] == 0) continue; // 剩余容量为 0，不在残量网络中，不遍历

                if (dis[y] < dis[x] + cost[i]) {
                    dis[y] = dis[x] + cost[i];
                    incf[y] = Math.min(incf[x], ed[i]);
                    pre[y] = i; // 记录前驱，便于找到最长路的实际方案
                    if (vis[y] == 0) {
                        vis[y] = 1;
                        q.add(y);
                    }
                }
            }
        }
        return dis[T] != -INF; // 汇点不可达，已求出最大流
    }

    void update() {
        int x = T;
        while (x != S) {
            int i = pre[x];
            ed[i] -= incf[T];
            ed[i ^ 1] += incf[T]; // 利用 成对存储 的 xor 1 技巧
            x = ver[i ^ 1];
        }
        maxflow += incf[T];
        ans += dis[T] * incf[T];
    }
}

（全文完）