保证绝大多数人的利益——匈牙利算法

$\color{red}\text{匈牙利算法}$是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来。（摘自[百度百科](https://baike.baidu.com/item/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/9089246?fr=aladdin)） 总的来说，匈牙利算法主要的用途是将多个任务尽可能多的分配给多个对象，在算法竞赛中主要用于求解二分图最大匹配等问题。 如果你不明白什么是二分图匹配，不妨看看下面这个例子。 幼儿园里现在有4个小朋友，摆在他们面前是四种食物，分别是棒冰、汉堡、薯片、炸鸡，现在要把这些食物分给小朋友们吃。根据调查，在我国改革开放、经济发展的前提下，现在的小朋友都吃得饱饭，所以他们都会挑食（~~但是好像没有人不吃垃圾食品~~）。他们的喜好大致是这样的：  我们把小朋友和食物看成分为两边的点，组成的图便是$\footnotesize\color{red}\text{二分图}$，而我们分配的过程就是$\footnotesize\color{red}\text{匹配}$。如果能把所有的食物都分配给小朋友，没有浪费，每个小朋友都开心，这自然是最吼的，这种情况也被称为$\footnotesize\color{red}\text{完美匹配}$。但事实显然不是次次都尽人意，所以只能让更多的小朋友开心，因为小朋友不高兴了实在是太麻烦了，开心的小朋友最多的情况就达到了$\footnotesize\color{red}\text{最大匹配}$。 为了让小朋友们感受异国风情，你决定受用匈牙利人的方法来分配。首先先考虑第1个小朋友，他喜欢棒冰，那就我们把棒冰给他。  接下来看第2个小朋友，他喜欢吃的是汉堡，而此时汉堡又名花无主，所以直接就把汉堡给他（汉堡：w(ﾟДﾟ)w）。  然后是3号小朋友，棒冰是他的最爱。等等！棒冰以及被1号小朋友拿走了！！！为了让3号小朋友不哭，我们决定从1号小朋友手中~~夺走~~拿来棒冰（1号小朋友：Σ(っ °Д °;)っ）。  （绿色表示棒冰暂时被拿走了） 看看1号小朋友能不能换一个东西吃，发现1号小朋友还喜欢汉堡，但是汉堡已经在2号小朋友的手中了，于是我们只好重复之前的步骤，发现最后可以让3个小朋友都开心，于是皆大欢喜。  最后是4号小朋友，我们试着给像对3号小朋友那样给4号小朋友分到他想要的食物，只是可惜没有成功。本着先到先得的原则，我们只好把暂时拿走的食物还给其他小朋友，留给4号小朋友的只有一个爱的抱抱了（4号小朋友：╥﹏╥...）。于是最终的情况变成了这样：  这样先到先得，尝试给后来的小朋友腾出食物，尽可能让更多小朋友开心的分配方式，就是用匈牙利算法求解二分图的最大匹配。 接下来是代码实现： ```cpp bool find(int now) { for(int i=head[now];i!=0;i=e[i].nxt) //使用邻接表储存边（小朋友喜好）的信息 if(vis[e[i].to]==false) //如果这个节点（食物）这次没有被调度过 { vis[e[i].to]=true; if(p[e[i].to]==0 || find(p[e[i].to])) //如果这个节点（食物）没有被匹配或者可以给这个现在匹配的节点（小朋友）找到一个新的匹配 { p[e[i].to]=now; return true; } } return false; //找不到就返回失败 } for(int i=1;i<=n;i++) //主程序 { memset(vis,false,sizeof(vis)); if(find(i)==true) ans++; } ``` 实现代码以后就是喜闻乐见的~~水~~好题推荐环节了！ [P3386 【模板】二分图匹配](https://www.luogu.org/problemnew/show/P3386) [P1640 [SCOI2010]连续攻击游戏](https://www.luogu.org/problemnew/show/P1640) [P3231 [HNOI2013]消毒](https://www.luogu.org/problemnew/show/P3231)