算法笔记——匈牙利算法

September 29, 2020 · python · 61次阅读

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

  • 男生和女生之间互相中意的,可以进行匹配
  • 男生中意的女生、女生中意的男生都可以不止一个
  • 要得到最多的匹配对数
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)

ENJOY 0

算法

最后编辑于1年前

添加新评论

avatar

未末

118

文章数

260

评论数

7

分类

新鲜出炉の评论

获取CSDN学院m3u8解密的key
路人甲
路人甲2021-10-05

请问这个方法失效了么?获取到的是空串

获取CSDN学院m3u8解密的key
DK爱梦游
DK爱梦游2021-09-29

大佬求教,51cto的KEY怎么获取?

XstreamDL-CLI BUG修复记录
poohboy
poohboy2021-09-25

大佬,我想问一下,iqiyi的m3u8是不是没法获取?我只找到了一个dash链接,然后手动下载了里面的m4s,但用nilaoda的那个解密工具解不了,老提示获取kid失败

XstreamDL-CLI BUG修复记录
Andist
Andist2021-09-17

en……实在不好意思,代理我知道怎么启用了。我只勾选了自定义代理,但没有填写proxy参数,我太愚钝了对不起!!!

XstreamDL-CLI BUG修复记录
Andist
Andist2021-09-17

感谢您开发的这款软件,对于第一次下载mpd的小白而言很友好! 这段时间用下来就是有时候下载直连的海外视频流时可能因为网络状况不佳,会有下载不完整的问题,下载完进度没到100%,但是也合并解密了,不知道能否增加下载不完整在最后输出报错信息的功能呢? 以及我想请教一下如何让下载器使用小飞机的代理呢?我尝试在“使用自定义代理”的选项上勾选,但是好像命令行中没有变化? (另外我猜您图中的样本是在下载CP+上的用九柑仔店是吗?我也很喜欢这部剧,是我心目中排名第一的台剧哈哈)