算法笔记——匈牙利算法

想象成左右两拨人，一边男一边女，然后进行匹配。

• 男生和女生之间互相中意的，可以进行匹配
• 男生中意的女生、女生中意的男生都可以不止一个
• 要得到最多的匹配对数

def test():
    def find(index: int):
        for j in range(girls):
            # 对于左侧的第i个男生 
            # 和右侧第j个女生可以匹配 
            # 并且此时第j个女生暂时没有匹配
            if relationships[index][j] is True and status[j] is False:
                # 将第j个女生标记为马上进行匹配
                status[j] = True
                # 如果第j个女生没有匹配结果 或者 之前匹配的那个男生可以找到新的女生进行匹配
                if res.get(j) is None or find(res[j]):
                    # 那就把当前第i个男生和第j个女生正式匹配
                    res[j] = index
                    # 返回匹配成功
                    return True
        # 返回匹配失败
        return False
    boys = 4
    girls = 4
    relationships = {
        0: [False, True, False, True],
        1: [False, True, False, False],
        2: [True, False, True, False],
        3: [False, False, False, True],
    }
    total = 0
    res = {} # 匹配结果
    for index in range(boys):
        status = [False] * girls
        if find(index):
            total += 1
    print(total, res)