二分图最大匹配，二分图带权匹配

打第五场牛客多校的时候发现KM的板子复杂度假了，特来补上，顺带复习一下

二分图最大匹配

匈牙利算法

交替路：从一个未匹配点出发，依次经过非匹配边，匹配边，非匹配边\(\cdots\)，形成的路径叫交替路。

增广路：途径交替路的起点之外的其他未匹配点的交替路叫做增广路。其一个重要性质是：非匹配边比匹配边多一条，因此交换增广路中的匹配边和非匹配边可以使匹配数+1。

增广路定理：当找不到增广路时，达到最大匹配。

匈牙利算法求最大匹配就是不断寻找增广路，每次找到增广路可以使匹配数+1，时间复杂度\(O(VE)\)，空间复杂度\(O(E)\)

UOJ #78 二分图最大匹配：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1007;
vector<int> adj[maxn];
bool vis[maxn]; //一次dfs过程中，右半边集合中的顶点是否已访问。
int ans[maxn], res[maxn];  //右半边集合中的点匹配的左半边点的编号。
int nl, nr, m;
bool dfs(int u) {
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (!vis[v]) {  //如果右半边的点v还未被访问
            vis[v] = true;
            if (ans[v] == -1 || dfs(ans[v])) {
                //如果v没有匹配点，或是v的匹配点能找到一条到未匹配点的增广路
                ans[v] = u;
                res[u] = v;
                return true;
            }
        }
    }
    return false;
}
int maxmatch() {
    int res = 0;
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= nl; i++) {
        memset(vis, 0, sizeof(vis));
        res += dfs(i);
    }
    return res;
}

int main() {
    cin >> nl >> nr >> m;
    for (int i = 1; i <= m; i++) {
        int v, u;
        scanf("%d%d",&v,&u);
        adj[v].push_back(u);
    }
    printf("%d\n", maxmatch());
    for (int i = 1; i <= nl; i++) {
        printf("%d ", res[i]);
    }
    return 0;
}

HK算法

UOJ上的榜一写的Hopcroft-Krap算法，9msAC，，，时间复杂度\(O(\sqrt{V}E)\)，实际速度很快

从hopcroft-karp算法 和二分图大讲堂——彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配 - One thing I know,that is I know nothing.(Socrates Greek) - ITeye博客学习一波

HK算法的流程如下：

用bfs对图进行分层，左部点中的所有未匹配点组成第一层，把经过的匹配点全部加入队列，直到所有未访问的匹配点都加入队列。（bfs保证了不相交且最短）然后使用dfs遍历bfs找出的所有增广路（按层次走），每条增广路可以使匹配数+1.不断重复bfs和dfs，直到找出了增广路。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1007, inf = 0x3f3f3f3f;
vector<int> adj[maxn];
int ansx[maxn], ansy[maxn], dx[maxn], dy[maxn], dis, nl, nr, m;
//ansx,ansy储存的分别是左边点和右边点对应的匹配点，dx和dy是bfs分出的层次，dis是当前bfs的增广路的长度
bool vis[maxn];
bool bfs() {
    queue<int> q;
    dis = inf;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
    //先找出左半边集合中的未匹配点作为bfs的源点
    for (int i = 1; i <= nl; i++) {
        if (ansx[i] == -1) {
            q.push(i);
            dx[i] = 0;
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dx[u] > dis) break; 
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (dy[v] == -1) {
                dy[v] = dx[u] + 1;
                if (ansy[v] == -1) dis = dy[v]; //每一轮bfs  增广路的长度+1
                else {
                    dx[ansy[v]] = dy[v] + 1;
                    q.push(ansy[v]);
                }
            }
        }
    }
    return dis != inf;
}
bool dfs(int u) {
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (!vis[v] && dy[v] == dx[u] + 1) {
            vis[v] = 1;
            //if (ansy[v] != -1 || dy[v] == dis) continue;
            if (ansy[v] == -1 || (dy[v] != dis && dfs(ansy[v]))) {
                ansy[v] = u;
                ansx[u] = v;
                return true;
            }
        }
    }
    return false;
}
int maxmatch() {
    int res = 0;
    memset(ansx, -1, sizeof(ansx));
    memset(ansy, -1, sizeof(ansy));
    while (bfs()) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= nl; i++) {
            if (ansx[i] == -1) 
                res += dfs(i);
        }
    }
    return res;
}
int main() {
    scanf("%d%d%d", &nl, &nr, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
    }
    printf("%d\n", maxmatch());
    for (int i = 1; i <= nl; i++) {
        printf("%d ", ansx[i] == -1 ? 0 : ansx[i]);
    }
}

最大流

略，复杂度\(O(n^{0.5}m)\)

二分图带权匹配

费用流要注意spfa会被卡（牛客多校5 J），dijkstra费用流没去试，m=n^2时应该也好不到哪里去

正确写法的KM算法是严格\(O(n^3)\)的

AcWing 375. 蚂蚁 - O(n^3) DFS版 KM算法 - AcWing

lyd给的真\(O(n^3)\)的dfs版KM

KM(匈牙利）算法：

P6577 【模板】二分图最大权完美匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

二分图最大权匹配 - OI Wiki (oi-wiki.org)

可以在\(O(n^3)\)的时间内求出二分图的最大权完美匹配；