TODO

前言

匈牙利算法记录，并且添加了几道实战题目

简介&思路

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径(是指从M中没有用到的顶点)开始，并从M中没有用到的顶点结束的交替路径)，它是一种用增广路径求二分图最大匹配的算法。

概念：

匹配&最大匹配&完美匹配

  1. 匹配：
    1. 一种边的集合，其中任意两条边没有公共顶点
  2. 最大匹配:
    1. 一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
  3. 完美匹配：
    1. 如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

交替路径&增广路径

  1. 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
  2. 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。

思路&实现

该思路和主要为最佳匹配问题，

题目

References