[模板] 二分图最大匹配

约定存边方式为从左部到右部的有向边,左右部点编号相同

匈牙利算法

lli mch[maxn];
lli vis[maxn];

bool dfs_hun(lli u, lli dfn) {
    if (vis[u] == dfn) return false;
    vis[u] = dfn;
    for (lli i = head[u]; ~i; i = edge[i].nxt) {
        lli v = edge[i].v;
        if (mch[v] == 0 || dfs_hun(mch[v], dfn)) {
            mch[v] = u;
            return true;
        }
    }
    return false;
}

lli ask_hun() {
    lli res = 0;
    for (lli i = 1; i <= n; ++i)
        if (dfs_hun(i, i))
            ++res;
    return res;
}

发表评论