二分图的判定及性质：

1) 静态二分图的判定： dfs染色
2) 动态二分图的判定： 扩展域并查集 / 带边权的并查集
3) 性质1：至少有2个顶点且没有奇环
4) 概念：最小点覆盖、最大独立集、最小路径点覆盖、最小路径重复点覆盖
5) 最大匹配数 = 最小点覆盖 = 总点数-最大独立集 = 总点数-最小路径覆盖
6) 最大匹配数 = 点数 - 最小不重复路径覆盖(这些相等关系注意理解证明)

konig定理：

二分图的最大匹配数等于最小点覆盖数

证明： 略

二分图的最大匹配：

1. 匈牙利算法（增广路算法）

"""
邻接矩阵存图时间复杂度为O(n^3)
邻接表存图时间复杂度为O(nm)
"""
#邻接表存图
def dfs(x):
    for y,w in g[x]:
        if vis[y]: continue  # 在dfs时注意两边集合的含义，如有特殊含义则需要增加判断条件
        vis[y] = True
        if not link[y] or dfs(link[y]):
            link[y] = x
            return True
    return False

ans = 0
link = [0]*(n+1)
for i in range(1,n+1):
    vis = [False]*(n+1)
    if dfs(i): ans += 1

二分图的最优(带权)匹配 —— KM ( Kuhn-Munkres ) 算法：

• 算法思路：最开始将每个左边节点连的权值最大的边视为有效边，在匹配给过程当中如果某个点找不到匹配点，则选择将一些无效边改成有效边继续去匹配，选择的这些无效边其实是换掉的原来的某条有效边，那么我们肯定选换掉的代价最小的。

• 具体操作：

1、给每个点预设一个顶标，只有两个端点的顶标加起来等于边权的边，我们才认为是有效边，即L[x]+R[y]==w[x][y]的时候才是有效边

2、最开始左集合的每个点的顶标为他连出去权值最大的边的权值，右集合每个点顶标为0，当匹配失败的时候，我们遍历之前的左集合本次尝试匹配遍历过的点，在他们的连向右集合未遍历的点的边中找一个与顶标和差值最小的边，即delta=w[x][y]-L[x]-R[y]最小的边（可理解为找出一条损失最小的找出一条增广路。）找到之后修改顶标：左侧所有遍历过的点减去delta，右边所有遍历过的点加上delta，这样原来的有效边还是有效边，而我们新加的边也已经加上了。

3、重复找匹配+修改顶标的操作，一直到找到一个完美匹配即可。

import sys

inf, _inf = float("inf"), float('-inf')
def km():
    def dfs(x):
        visx[x] = 1
        for i in range(1,H+1):
            if not visy[i] and lx[x] + ly[i] == g[x][i]:  #两顶标相加等于边权为有效边
                visy[i] = 1
                if link[i] == 0 or dfs(link[i]):
                    link[i] = x
                    return 1
        return 0
    
    for i in range(1,P+1):
        while True:
            visx,visy = [0]*(P+1), [0]*(H+1)
            if dfs(i): break
            d = inf
            for j in range(1,P+1):
                if visx[j]:
                    for k in range(1,H+1):
                        if not visy[k]: d = min(d, lx[j] + ly[k] - g[j][k])
            if d == inf: return 0
            for j in range(1,P+1):
                if visx[j]: lx[j] -= d
            for j in range(1,H+1):
                if visy[j]: ly[j] += d
    return 1

"""P为人的数量，H为房子的数量，人和房子分别为左右集合"""
    lx,ly,link = [_inf]*(P+1),[0]*(H+1),[0]*(P+1)
    for i in range(1,P+1):
        for j in range(1,H+1):
            if g[i][j] != 0:
                lx[i] = max(lx[i], g[i][j])
    if km() == 1:
        ans = 0
        for i in range(1,H+1):
            ans += g[link[i]][i] #link记录了每个房子（右集合）匹配到的人的下标（左集合）
        print(-ans)   #题目求的是最小匹配，我们将边取负，求最大匹配，输出相反数