匈牙利算法 | Hungarian

_dijkstra_ · 2022-12-26 14:42:46 · 个人记录

bool dfs(int u)
{
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].now;
        if (vis[v]) continue;
        vis[v] = true;
        if (!match[v] || dfs(match[v])) {match[v] = u; return true;}
    }
    return false;
}

for (int i = 1; i <= m; i++)
{
    memset(vis, false, sizeof vis);
    if (dfs(i)) ans++;
}