图匹配python模板

二分图的判定算法模板

二分图的判定及性质：

1) 静态二分图的判定： dfs染色
2) 动态二分图的判定： 扩展域并查集 / 带边权的并查集
3) 性质1：至少有2个顶点且没有奇环
4) 性质2：最小路径覆盖 = 顶点数 - 最大匹配

konig定理：

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

匈牙利算法模板

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

"""
邻接矩阵存图时间复杂度为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算法模板

• 算法思路：

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

• 具体操作：

1、给每个点预设一个顶标，只有两个端点的顶标加起来等于边权的边，我们才认为是有效边，即的时候才是有效边

2、最开始左集合的每个点的顶标为他连出去权值最大的边的权值，右集合每个点顶标为0，当匹配失败的时候，我们枚举之前的左集合本次尝试匹配遍历过的点，在他们的连向右集合未遍历的点的边中找一个与顶标和差值最小的边（即在当前的无效边中找一个差值最小的边），即 最小的边（可理解为找出一条损失最小的找出一条增广路。）找到之后修改顶标：左侧所有枚举过的点减去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 1:
            visx,visy = [0]*(P+1), [0]*(H+1)
            if dfs(i): break
            d = inf
            for j in range(1,P+1):
                if visx[j]:  # 枚举所有左集合访问过的点，找到差值最小的 d
                    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)   # 题目求的是最小匹配，我们将边取负，求最大匹配，输出相反数

稳定婚姻类问题思路

可以通俗的理解为有n个男生，n个女生，每个人都每个异性都有 一个好感度，要求两两配对结为夫妻，使不存在夫妻uv和ab，满足u对b的好感度大于u对v的好感度，b对u的好感度大于b对a的 好感度。求这种稳定婚姻的方案。

Gale-Shapley算法

• 首先，男生需要按照希望与之交往的顺序给所有女生排序，即最理想 的女友排在最前、最不理想的放在最后。同样，每个女生也需要给男 生排序。接着，男生将按照自己的名单一轮一轮地去追求喜欢的女生， 女生也将按照自己的名单接受或拒绝对方的追求。

• 第一轮，每个男生都向自己名单上排在首位的女生表白。此时，一个 女生可能面对的情况有三种：没有人跟她表白、只有一人跟她表白、 有不止一人跟她表白。在第一种情况下，这个女生什么都不做，继续 等待即可；在第二种情况下，女生接受那个人的表白，答应暂时和他 做男女朋友；在第三种情况下，女生从所有追求者中选择自己最喜欢 的那一位，答应和他暂时做男女朋友，并拒绝其他所有的追求者。

• 第一轮结束后，有些男生已经有女朋友了而有些男生仍然是单身狗。在第二轮表白 行动中，每个单身男都会从所有还没拒绝过自己的女生中选出自己最喜欢的那一个， 并向她表白，不管她现在是否是单身。和第一轮一样，每个被表白的女生需要从表 白者中选择最喜欢的男生，并拒绝其他追求者。注意，如果这个女生当前已经有男 朋友了，当她遇到了更好的追求者时，她将毫不犹豫地和现男友分手，投向新追求 者的怀抱。这样以来，一些单身狗将脱单，而一些倒霉的恩爱狗（男）也会被分手， 重新进入单身狗的行列。

• 在以后的每一轮中，单身狗们将发扬愈挫愈勇的顽强精神，继续追求列表中的下 一个女生；女生则从包括现男友在内的所有追求者中选择最好的一个，并给其他所 有追求者发好人卡。这样一轮一轮地进行下去，直到某个时刻所有人都不再单身， 那么下一轮将不会有任何新的表白，每个人的对象也都将固定下来，整个过程自动 结束——此时的搭配就一定是稳定的了。

一般图匹配算法模板(带花树问题)

待更新