jly 的模板

struct MCFGraph {
    struct Edge {
        int v, c, f;
        Edge(int v, int c, int f) : v(v), c(c), f(f) {}
    };
    const int n;
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<i64> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, std::numeric_limits<i64>::max());
        pre.assign(n, -1);
        std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            i64 d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] < d) continue;
            for (int i : g[u]) {
                int v = e[i].v;
                int c = e[i].c;
                int f = e[i].f;
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<i64>::max();
    }
    MCFGraph(int n) : n(n), g(n) {}
    void addEdge(int u, int v, int c, int f) {
        if (f < 0) {
            g[u].push_back(e.size());
            e.emplace_back(v, 0, f);
            g[v].push_back(e.size());
            e.emplace_back(u, c, -f);
        } else {
            g[u].push_back(e.size());
            e.emplace_back(v, c, f);
            g[v].push_back(e.size());
            e.emplace_back(u, 0, -f);
        }
    }
    std::pair<int, i64> flow(int s, int t) {
        int flow = 0;
        i64 cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) h[i] += dis[i];
            int aug = std::numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= aug;
                e[pre[i] ^ 1].c += aug;
            }
            flow += aug;
            cost += i64(aug) * h[t];
        }
        return std::make_pair(flow, cost);
    }
};

最大流最小费模板

在 2850. 将石头分散到网格图的最少移动次数 2896. 执行操作使两个字符串相等 都可以用这个模板过，设置好虚拟源点和终点（max 编号+1），搞清楚加边的容量和费用，套进去就可以了，目前看来都是用在二分图上（搞清楚题目能不能转化为二分图）

template<typename K>
class MCMF {
    // he: 头 ne: 链表 e: 终点 cap: 容量 dep: 分层 cur: 当前弧
    vector<int> he, ne, e, vis, cur, inq;
    vector<K> cap, cost, dis;
    int n, m, S, T;
    K INF;
public:
    MCMF(int n_, int S_, int T_) : n(n_), S(S_), T(T_) {
        memset(&INF, 0x3f, sizeof INF);
        he.resize(n, -1);
        dis.resize(n);
        inq.resize(n);
        vis.resize(n, 0);
        cur.resize(n);
    }
    /**
     * @param w 容量
     * @param c 费用
     */
    void addEdge(int a, int b, K _cap, K _cost) {
        cap.emplace_back(_cap), cost.emplace_back(_cost);
        ne.emplace_back(he[a]), he[a] = e.size(), e.emplace_back(b);
        cap.emplace_back(0), cost.emplace_back(-_cost);
        ne.emplace_back(he[b]), he[b] = e.size(), e.emplace_back(a);
    }

    bool spfa() {
        queue<int> q({S});
        fill(begin(dis), end(dis), INF);
        fill(begin(inq), end(inq), 0);
        cur = he;
        dis[S] = 0, cur[S] = he[S], inq[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (auto i = he[u]; ~i; i = ne[i]) {
                int v = e[i];
                if (cap[i] && dis[u] + cost[i] < dis[v]) {
                    dis[v] = dis[u] + cost[i];
                    if (!inq[v]) {
                        q.emplace(v);
                        inq[v] = 1;
                    }
                }
            }
        }
        return dis[T] != INF;
    }

    K find(int u, K limit) {
        if (u == T)
            return limit;
        vis[u] = 1;
        K flow = 0;
        for (auto i = cur[u]; ~i && flow < limit; i = ne[i]) {
            cur[u] = i;
            int v = e[i];
            if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
                K t = find(v, min(cap[i], limit - flow));
                cap[i] -= t, cap[i ^ 1] += t, flow += t;
            }
        }
        vis[u] = 0;
        return flow;
    }

    pair<K, K> run() {
        K maxflow = 0, mincost = 0;
        while (spfa()) {
            K t = find(S, INF);
            maxflow += t;
            mincost += t * dis[T];
        }
        return {maxflow, mincost};
    }
};
// 2896
class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        int n = s1.size();
        vector<int> p;
        for (int i = 0; i < n; i++)
            if (s1[i] != s2[i]) p.push_back(i);
        int m = p.size();
        if (m % 2) return -1;
        int src = m, dst = m + 1;
        MCMF<int> mcf(n + 2, src, dst);
        for (int i = 0; i < m; i++)
            if (i % 2 == 0) mcf.addEdge(src, i, 1, 0);
            else mcf.addEdge(i, dst, 1, 0);
        for (int i = 0; i < m; i += 2)
            for (int j = 1; j < m; j += 2)
                mcf.addEdge(i, j, 1, min(abs(p[j] - p[i]), x));
        return mcf.run().second;
    }
};
// 2850
class Solution {
public:
    int minimumMoves(vector<vector<int>>& g) {
        int S = 18, T = 19;
        MCMF<int> mcf(20, S, T);
        int id = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                mcf.addEdge(i * 3 + j + 9, T, 1, 0);
                for (int k = 0; k < g[i][j]; ++k, ++id) {
                    mcf.addEdge(S, id, 1, 0);
                    for (int x = 0; x < 3; ++x) {
                        for (int y = 0; y < 3; ++y) {
                            int t = x * 3 + y + 9;
                            mcf.addEdge(id, t, 1, abs(x - i) + abs(y - j));
                        }
                    }
                }
            }
        }
        return mcf.run().second;
    }
};