Qiuxotic's Blog

匈牙利匹配算法

最大二分匹配 解决问题 找到连接二部图中最多的边数。通常与订单匹配,共享出行的人车匹配相关 算法思想 先找到一条增广路,然后在增广路的基础上取反,即可以多得到一条边。 增广路的前置概念是交替路,什么是交替路呢?顾名思义是交替出现匹配与未匹配的路径。增广路的要求更严格一点,需要从未匹配的边开始,然后经过交替路径最后也是未匹配的边。 在这张图中,C->E->A->F-...