匈牙利算法

约定不等于承诺〃 2022-04-22 07:22 174阅读 0赞

匈牙利算法就是匹配最大度的问题

max_node =100
    bigraph=[[ False for i  in range(max_node)]for  j in range(max_node)]
    parent=[False for   i in range(max_node)]
    visited =[ False for j in range(max_node)]
    
    result={}
    max_matching = 0
    x_node = int(input("please input the num of  x_node:   "))
    y_node = int(input("please input the num of  y_node:   "))
    edge_num = int(input("please input the num of edge: "))
    for i in range(edge_num):
         start_node , end_node =map(lambda  x:int(x),input(" enter the start_node and end_node(split by space):  ").split(" "))
         bigraph[start_node][end_node]=True
    def find_argumenting_path(start_node):
        for next_node in range(1,1+y_node):
            if not visited[next_node] and bigraph[start_node][next_node]:
                visited[next_node]=True
                if not parent[next_node] or find_argumenting_path(next_node):
                           parent[next_node]=start_node
                           result[start_node]=[next_node]
                           return True
        return False
    
    for node in range(1,1+x_node):
        visited = [False for j in range(max_node)]
        if find_argumenting_path(node):
              max_matching+=1
    
    print(max_matching)
    print(result)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70]: /images/20220422/4c43510aea464706be303f107ba2ce65.png

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关匈牙利算法模板

题目背景二分图感谢@一扶苏一提供的hack数据题目描述给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数输入格式第一行...

古城微笑少年丶/ 2024年04月19日 15:40/ 0 赞/ 69 阅读

相关匈牙利算法总结

指派问题概述：有n项不同的任务，需要n个人分别完成其中的1项，每个人完成任务的时间不一样。于是就有一个问题，如何分配任务使得花费时间最少。通俗来讲，就是n\n矩阵中，选取n个元

﹏ヽ暗。殇╰゛Y/ 2023年06月27日 12:55/ 0 赞/ 28 阅读

相关算法笔记【6】匈牙利算法

算法笔记【6】匈牙利算法匈牙利算法简介今天我们来看一个没有前几篇讲的那么常用，但是很有用的算法：匈牙利算法（Hungarian algorithm）。匈牙利算

一时失言乱红尘/ 2023年01月11日 01:25/ 0 赞/ 115 阅读

相关匈牙利算法

匈牙利算法：月老准备给n个女孩与n个男孩牵红线，成就一对对美好的姻缘。现在，由于一些原因，部分男孩与女孩可能结成幸福的一家，部分可能不会结成幸福的家庭。现在已知

桃扇骨/ 2022年10月01日 00:51/ 0 赞/ 146 阅读

相关利用python解决指派问题（匈牙利算法）

前言：最近在备战数模，看到了指派问题，饶有兴趣，百度上找了很多关于指派问题的解法，很明显用的是匈牙利算法，手工的计算，各种各种的博客都很详尽，大概都了解了具体原理（不懂的人可以

梦里梦外;/ 2022年06月01日 08:43/ 0 赞/ 158 阅读

相关匈牙利算法

匈牙利算法就是匹配最大度的问题 max_node =100 bigraph=[[ False for i in range(max_node)]for

约定不等于承诺〃/ 2022年04月22日 07:22/ 0 赞/ 175 阅读

相关二分图匹配——匈牙利算法

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是

小咪咪/ 2022年01月23日 20:55/ 0 赞/ 695 阅读

相关 hdu1528匈牙利算法---邻接矩阵

赤裸裸的二分匹配。。。注意处理好输入 \include<cstdlib> \include<iostream> \include<cstring> using

左手的ㄟ右手/ 2022年01月17日 04:13/ 0 赞/ 231 阅读

相关 Pets（匈牙利算法）

Are you interested in pets? There is a very famous pets shop in the center of the ACM ci

女爷i/ 2021年10月29日 15:16/ 0 赞/ 317 阅读

相关二分图匹配：匈牙利算法

日常打板子..最近做题是有点太少了啦要加油了呢x 二分图匹配我找到了一篇对定义说的非常详细的博文贴一下( 转自http://www.renfei.org/blog/bi

悠悠/ 2021年09月30日 11:18/ 0 赞/ 550 阅读