xi. Weighted General Matching

Maximum-weight matching in a general graph: Edmonds’ blossom algorithm with dual variables (primal–dual), $O(n^3)$ with an adjacency matrix, $n\le 500$ or so. For bipartite graphs use the Hungarian algorithm (Assignment Problem); for $n\le 20$ a bitmask DP is simpler.

Variant	Reduction
maximum weight matching (any size)	the code below, weights $>0$ (drop non-positive edges)
maximum weight among maximum cardinality matchings	add $C=1+\sum w$ to every weight
minimum weight perfect matching	weight $C-w_e$ with $C > \sum
Chinese postman, T-joins	odd-degree vertices, shortest-path distances, min-weight perfect matching (Euler Tours)
$n\le 20$	DP over subsets pairing the lowest unpaired vertex, $O(2^{n}n)$

struct WeightedBlossom {                                      // maximum weight matching, weights > 0, O(n^3)
    struct E { int u, v; ll w; };
    int N, NX; vector<vector<E>> g; vector<ll> lab;
    vector<int> match, slack, st, par, S, aux; vector<vector<int>> floFrom, flo; queue<int> q; int stamp = 0;
    WeightedBlossom(int n) : N(n), NX(n), g(2 * n + 1, vector<E>(2 * n + 1)), lab(2 * n + 1), match(2 * n + 1), slack(2 * n + 1),
        st(2 * n + 1), par(2 * n + 1), S(2 * n + 1), aux(2 * n + 1), floFrom(2 * n + 1, vector<int>(n + 1)), flo(2 * n + 1) {
        for (int u = 1; u <= N; u++) for (int v = 1; v <= N; v++) g[u][v] = {u, v, 0};
    }
    void addEdge(int u, int v, ll w) {                       // 0-indexed; keeps the heaviest parallel edge
        u++, v++; if (u == v) return;
        w = max(w, g[u][v].w); g[u][v].w = g[v][u].w = w;
    }
    ll eDelta(const E& e) const { return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2; }
    void updSlack(int u, int x) { if (!slack[x] || eDelta(g[u][x]) < eDelta(g[slack[x]][x])) slack[x] = u; }
    void setSlack(int x) { slack[x] = 0; for (int u = 1; u <= N; u++) if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) updSlack(u, x); }
    void qPush(int x) { if (x <= N) q.push(x); else for (int t : flo[x]) qPush(t); }
    void setSt(int x, int b) { st[x] = b; if (x > N) for (int t : flo[x]) setSt(t, b); }
    int getPr(int b, int xr) {
        int pr = find(all(flo[b]), xr) - flo[b].begin();
        if (pr & 1) { reverse(flo[b].begin() + 1, flo[b].end()); return sz(flo[b]) - pr; }
        return pr;
    }
    void setMatch(int u, int v) {
        E e = g[u][v]; match[u] = e.v;
        if (u <= N) return;
        int xr = floFrom[u][e.u], pr = getPr(u, xr);
        for (int i = 0; i < pr; i++) setMatch(flo[u][i], flo[u][i ^ 1]);
        setMatch(xr, v); rotate(flo[u].begin(), flo[u].begin() + pr, flo[u].end());
    }
    void augment(int u, int v) {
        for (;;) {
            int xnv = st[match[u]]; setMatch(u, v);
            if (!xnv) return;
            setMatch(xnv, st[par[xnv]]); u = st[par[xnv]], v = xnv;
        }
    }
    int lca(int u, int v) {
        for (++stamp; u || v; swap(u, v)) {
            if (!u) continue;
            if (aux[u] == stamp) return u;
            aux[u] = stamp; u = st[match[u]];
            if (u) u = st[par[u]];
        }
        return 0;
    }
    void addBlossom(int u, int anc, int v) {
        int b = N + 1;
        while (b <= NX && st[b]) ++b;
        if (b > NX) ++NX;
        lab[b] = S[b] = 0; match[b] = match[anc]; flo[b] = {anc};
        auto blossom = [&](int x) { for (int y; x != anc; x = st[par[y]]) flo[b].push_back(x), flo[b].push_back(y = st[match[x]]), qPush(y); };
        blossom(u); reverse(flo[b].begin() + 1, flo[b].end()); blossom(v);
        setSt(b, b);
        for (int x = 1; x <= NX; x++) g[b][x].w = g[x][b].w = 0;
        for (int x = 1; x <= N; x++) floFrom[b][x] = 0;
        for (int xs : flo[b]) {
            for (int x = 1; x <= NX; x++) if (g[b][x].w == 0 || eDelta(g[xs][x]) < eDelta(g[b][x])) g[b][x] = g[xs][x], g[x][b] = g[x][xs];
            for (int x = 1; x <= N; x++) if (floFrom[xs][x]) floFrom[b][x] = xs;
        }
        setSlack(b);
    }
    void expandBlossom(int b) {
        for (int t : flo[b]) setSt(t, t);
        int xr = floFrom[b][g[b][par[b]].u], pr = getPr(b, xr);
        for (int i = 0; i < pr; i += 2) {
            int xs = flo[b][i], xns = flo[b][i + 1];
            par[xs] = g[xns][xs].u; S[xs] = 1; S[xns] = slack[xs] = slack[xns] = 0; qPush(xns);
        }
        S[xr] = 1, par[xr] = par[b];
        for (int i = pr + 1; i < sz(flo[b]); i++) { int xs = flo[b][i]; S[xs] = -1; setSlack(xs); }
        st[b] = 0;
    }
    bool onFoundEdge(const E& e) {
        int u = st[e.u], v = st[e.v];
        if (S[v] == -1) {
            par[v] = e.u, S[v] = 1; slack[v] = 0;
            int nu = st[match[v]]; S[nu] = slack[nu] = 0; qPush(nu);
        } else if (S[v] == 0) {
            int anc = lca(u, v);
            if (!anc) { augment(u, v), augment(v, u); return true; }
            addBlossom(u, anc, v);
        }
        return false;
    }
    bool matching() {
        q = queue<int>();
        for (int x = 1; x <= NX; x++) { S[x] = -1, slack[x] = 0; if (st[x] == x && !match[x]) par[x] = S[x] = 0, qPush(x); }
        if (q.empty()) return false;
        for (;;) {
            while (sz(q)) {
                int u = q.front(); q.pop();
                if (S[st[u]] == 1) continue;
                for (int v = 1; v <= N; v++) if (g[u][v].w > 0 && st[u] != st[v]) {
                    if (eDelta(g[u][v]) == 0) { if (onFoundEdge(g[u][v])) return true; }
                    else updSlack(u, st[v]);
                }
            }
            ll d = LLONG_MAX;
            for (int b = N + 1; b <= NX; b++) if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
            for (int x = 1; x <= NX; x++) if (st[x] == x && slack[x]) {
                if (S[x] == -1) d = min(d, eDelta(g[slack[x]][x]));
                else if (S[x] == 0) d = min(d, eDelta(g[slack[x]][x]) / 2);
            }
            for (int u = 1; u <= N; u++) {
                if (S[st[u]] == 0) { if (lab[u] <= d) return false; lab[u] -= d; }
                else if (S[st[u]] == 1) lab[u] += d;
            }
            for (int b = N + 1; b <= NX; b++) if (st[b] == b && S[b] != -1) lab[b] += (S[b] == 0 ? 1 : -1) * d * 2;
            q = queue<int>();
            for (int x = 1; x <= NX; x++)
                if (st[x] == x && slack[x] && st[slack[x]] != x && eDelta(g[slack[x]][x]) == 0 && onFoundEdge(g[slack[x]][x])) return true;
            for (int b = N + 1; b <= NX; b++) if (st[b] == b && S[b] == 1 && lab[b] == 0) expandBlossom(b);
        }
    }
    pair<ll, int> solve() {                                   // {total weight, number of matched pairs}
        NX = N; st[0] = 0; fill(all(aux), 0);
        for (int i = 1; i <= N; i++) match[i] = 0, st[i] = i, flo[i].clear();
        ll wMax = 0;
        for (int u = 1; u <= N; u++) for (int v = 1; v <= N; v++) floFrom[u][v] = u == v ? u : 0, wMax = max(wMax, g[u][v].w);
        for (int u = 1; u <= N; u++) lab[u] = wMax;
        int num = 0; while (matching()) ++num;
        ll wei = 0;
        for (int u = 1; u <= N; u++) if (match[u] && match[u] < u) wei += g[u][match[u]].w;
        return {wei, num};
    }
    int mate(int v) const { return match[v + 1] ? match[v + 1] - 1 : -1; }
};

The labels start at $\max w$ and only decrease; the search stops when a free vertex’s label would reach 0, so the result maximises weight, not size. Vertices are 0-indexed outside, 1-indexed inside; super-vertices $N+\mathrm{1..2}N$ are blossoms.

ll maxWeightMatchingDP(int n, const vector<vector<ll>>& w) {  // w[u][v] (<= 0 means "no edge"), n <= 20
    vector<ll> dp(1 << n, 0);                                 // dp[mask]: best on the vertex set mask
    for (int mask = 1; mask < (1 << n); mask++) {
        int v = __builtin_ctz(mask), rest = mask & ~(1 << v);
        dp[mask] = dp[rest];                                  // v stays unmatched
        for (int u = v + 1; u < n; u++) if (rest >> u & 1 && w[v][u] > 0) dp[mask] = max(dp[mask], w[v][u] + dp[rest & ~(1 << u)]);
    }
    return dp[(1 << n) - 1];
}

Proof sketch: primal–dual correctness

LP. Edmonds’ theorem: the matching polytope is described by $x_e\ge 0$, ${\sum }_{e\ni v}{x}_e\le 1$, and ${\sum }_{e\subseteq B}{x}_e\le \lfloor |B|/2\rfloor$ for every odd set $B$. The dual has $y_v\ge 0$ and $z_B\ge 0$ with $y_u+y_v+{\sum }_{B\ni u,v}{z}_B\ge w_{uv}$, minimising $\sum y_v+{\sum }_B\lfloor |B|/2\rfloor z_B$. In the code lab[v] is $2y_v$ and lab[b] is $2z_b$ (doubling keeps everything integral), and eDelta is twice the slack of an edge (blossom terms enter through st).

Invariants. All duals are non-negative and every edge has slack $\ge 0$; matched edges and blossom edges are tight; only blossoms with $z_B>0$ exist (outer blossoms with label 0 are expanded). Each round grows alternating trees from all free vertices along tight edges, shrinks a blossom when two outer vertices of the same tree meet, and augments when two trees meet. When stuck, the dual change $d$ lowers outer vertex labels and raises inner ones (and adjusts blossom labels oppositely), which keeps tree edges tight and all slacks non-negative, and $d$ is the largest step that keeps that true, so a new tight edge appears or an inner blossom’s label reaches 0 and it is expanded. The step is stopped when free vertices’ labels hit 0.

Optimality (complementary slackness). At termination: matched edges are tight; every vertex with $y_v>0$ is matched (free vertices are outer and all have reached $y_v=0$, because the labels of all free vertices decrease together from the same start); every blossom with $z_B>0$ is full ($\lfloor |B|/2\rfloor$ matched edges inside). Then the primal value equals the dual value, so the matching is optimal by weak duality. Each augmentation happens after $O(n)$ dual steps of $O(n^2)$ each in a dense implementation, and there are $\le n/2$ augmentations: $O(n^3)$ with this bookkeeping (the classic analysis charges $O(n)$ stages each costing $O(n^2)$).

Proof: the reductions

Max cardinality first: with $C>\sum w$, a matching with $k$ edges weighs between $kC$ and $kC+\sum w<(k+1)C$, so a heavier matching never has fewer edges, and among equal sizes the original weights decide. Min-weight perfect: weights $C-w_e$ with $C>\sum |w|$ are positive; a perfect matching weighs $\frac{n}{2}C-w(M)$, every non-perfect one at most $(\frac{n}{2}-1)C+\sum |w|<\frac{n}{2}C-\sum |w|$, so the maximum is a perfect matching (if one exists) of minimum original weight. DP: the lowest vertex of the remaining set is either unmatched or matched to some $u$ in the set; both cases leave a smaller set, so the recurrence enumerates all matchings.