$\mathcal{Description}$

Link.

给定二分图 $G=(V=X\cup Y,E)$，$|X|=|Y|=n$，边 $(u,v)\in E$ 有权 $w(u,v)$，且保证存在完美匹配。求 $G$ 的一个匹配 $M$，最大化 $\sum_{(u,v)\in M}w(u,v)$。

$n\le500$。

$\mathcal{Solution}$

首先我会费用流。

Kuhn-Munkres 算法，能够在 $\mathcal O(n^3)$ 的优秀复杂度内解决这一问题，即二分图最大权完美匹配问题。

定义 1（可行顶标） 对于 $u\in V$，分配一个实数顶标 $l(u)$，若满足 $\forall (u,v)\in E,w(u,v)\le l(u)+l(v)$，则称 $l$ 为可行顶标。

定义 2（相等子图） 在确定的可行顶标 $l$ 下，定义 $G$ 的相等子图 $H=(V,E')$，其中 $E'=\{(u,v)\in E\mid w(u,v)=l(u)+l(v)\}$。

定理 1 若相等子图 $H$ 有完美匹配 $M$，则 $M$ 是 $G$ 的最大权完美匹配。

定理的证明是平凡的，不过值得一提的是，$\sum l(u)$ 与 $\sum w(u,v)x(u,v)$（$x(u,v)\in\{0,1\}$，表示这条边选或不选）似乎构成对偶线性规划的关系，期待读者能在此有一些思考（咕。

接下来就落实到算法层面，我们的目标就是找到存在完美匹配的可行顶标。

首先，任取一组可行顶标。例如，$l(u)=[u\in X]\max_{(u,v)\in E}w(u,v)$。

此后，选一个未匹配点，走交错路径增广。若存在增广路就直接增广；否则，我们会通过遍历得到一棵交错路径树。令 $S,T$ 分别表示 $X,Y$ 中在树上的点，$S',T'$ 则表示不在树上的点。分析集合到集合内边的性质：

$\forall u\in S,v\in T',(u,v)\in E,~w(u,v)<l(u)+l(v) $。
$\forall u\in S',v\in T,(u,v)\in E$，$(u,v)$ 不是匹配边。

考虑这样一个对 $l$ 的调整，取某个正整数 $d$，令

\[l'(u)=\begin{cases}
l(u) & u\in S'\cup T'\\
l(u)-d & u\in S\\
l(u)+d & u\in T
\end{cases}.
\]

考查新的 $l'$ 带来的影响：

$(u,v)\in S\times T$ 内的边，$l(u)+l(v)$ 不变，不影响。
$(u,v)\in S'\times T'$ 内的边，也不影响。
$(u,v)\in S\times T'$，顶标的限制从 $l(u)+l(v)$ 变为 $l(u)+l(v)-d$，则 $(u,v)$ 有可能加入 $H$。
$(u,v)\in S'\times T$，顶标的限制从 $l(u)+l(v)$ 变为 $l(u)+l(v)+d$，则 $(u,v)$ 不可能加入 $H$。

可见，仅有 $S\times T'$ 内的边影响 $l'$ 的可行性。我们取 $d=\min_{(u,v)\in E\cap (S\times T')}\{l(u)-l(v)-w(u,v)\}$，则必然至少一条边进入 $H$，就能借此扩展交错路径树了。对于 $u\in Y$，通过维护 $s(u)=\min\{l(u)-l(v)-w(u,v)\}$，就能快速求出 $d$。

分析复杂度，$n$ 次枚举起始点，每次做至多 $n$ 次对 $l'$ 的更新，每次更新 $\mathcal O(n)$，最终可以做到 $\mathcal O(n^3)$。

$\mathcal{Code}$

注意几个细节：

$l(u),s(u)$ 的规模可能很大，上界为 $nw$，$w$ 为边权，上界是能达到的。
增广时必须从新连入交替路径树的点出发以保证复杂度。

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)

#define per(i, r, l) for (int i = r, per##i = r; i >= per##i; --i)

typedef long long LL;

template <typename Tp>

inline Tp imin(const Tp& u, const Tp& v) { return u < v ? u : v; }

template <typename Tp>

inline Tp imax(const Tp& u, const Tp& v) { return u < v ? v : u; }

const int MAXN = 500;

const LL LINF = 0x3f3f3f3f3f3f3f3f;

int n, m, fa[MAXN * 2 + 5], mtc[MAXN * 2 + 5];

LL slk[MAXN * 2 + 5], lab[MAXN * 2 + 5], adj[MAXN + 5][MAXN + 5];

bool vis[MAXN * 2 + 5];

inline int augment(const int u, std::vector<int>& newS) {

    assert(!vis[u]), vis[u] = true;

    if (u > n && !mtc[u]) return u;

    else if (u > n) {

        if (int t; fa[mtc[u]] = u, t = augment(mtc[u], newS)) return t;

    } else {

        newS.push_back(u);

        rep (v, n + 1, n << 1) {

            if (!vis[v] && adj[u][v - n] == lab[u] + lab[v]) {

                if (int t; fa[v] = u, t = augment(v, newS)) {

                    return t;

                }

            }

        }

    }

    return 0;

}

inline LL kuhnMunkres() {

    LL ret = 0;

    rep (u, 1, n) rep (v, 1, n) lab[u] = imax(lab[u], 0ll + adj[u][v]);

    rep (u, 1, n) if (!mtc[u]) {

        int fin, cur = u;

        static std::vector<int> newS; newS.clear();

        memset(fa, 0, sizeof fa);

        memset(vis, false, sizeof vis);

        memset(slk, 0x3f, sizeof slk);

        while (!(fin = augment(cur, newS))) {

            LL d = LINF;

            rep (v, n + 1, n << 1) if (!vis[v]) {

                for (int u: newS) {

                    if (LL t = lab[u] + lab[v] - adj[u][v - n]; t < slk[v]) {

                        slk[v] = t, fa[v] = u;

                    }

                }

                d = imin(d, slk[v]);

            }

            newS.clear(), cur = 0;

            rep (u, 1, n) if (vis[u]) lab[u] -= d;

            rep (v, n + 1, n << 1) {

                if (vis[v]) lab[v] += d;

                else if (!(slk[v] -= d)) cur = v;

            }

        }

        if (fin) {

            for (int v = fin, u = fa[v]; u; u = fa[v = fa[u]]) {

                mtc[u] = v, mtc[v] = u;

                ret += adj[u][v - n];

                if (fa[u]) ret -= adj[u][fa[u] - n];

            }

        }

    }

    return ret;

}

int main() {

    scanf("%d %d", &n, &m);

    rep (i, 1, n) rep (j, 1, n) adj[i][j] = -LINF;

    rep (i, 1, m) {

        int u, v, w; scanf("%d %d %d", &u, &v, &w);

        adj[u][v] = w;

    }

    printf("%lld\n", kuhnMunkres());

    rep (v, n + 1, n << 1) printf("%d%c", mtc[v], v < repv ? ' ' : '\n');

    return 0;

}

巴特西

Solution -「洛谷 P6577」「模板」二分图最大权完美匹配

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章