分类：匈牙利算法

2022
03-17

C++ 匈牙利算法案例分析详解

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。-------等等，看得头大？那么请看下面的版本：通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（-_-||暂时不考虑特殊的... 继续阅读 >

2021
09-06

详解C++实现匈牙利算法

目录一、匈牙利算法介绍二、最大匹配问题三、最小点覆盖问题四、匈牙利算法的应用4.1、（洛谷P1129）[ZJOI2007]矩阵游戏4.2、（vijos1204）CoVH之柯南开锁4.3、（TYVJP1035）棋盘覆盖一、匈牙利算法介绍匈牙利算法（Hungarianalgorithm）主要用于解决一些与二分图匹配有关的问题，所以我们先来了解一下二分图。二分图（Bipartitegraph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图... 继续阅读 >