这就是NTR算法 ？？ 渣男渣女算法 ？？
接下来要介绍的NTR算法，啊呸，不对不对，匈牙利算法，是一种确定二分图的最大匹配数量的一种非常高效的算法；
我们先介绍一下二分图的匹配以及最大匹配：
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
换言之，二分图的匹配就是点与点之间一 一对应，最大匹配就是一 一对应的个数能有多大；
接下来，我们将介绍y总的奇妙比喻：我们把不同点集之间的匹配比作男女生找对象，就假设左边是男生，右边是女生好了，如果两者之间有一条边，就说明这俩互相有crush，能撮合到一起；
我们的角色就是月老，我们想让尽可能多的情侣出现，所以我们遍历男生，这个男生的所有边都是可能是他的女朋友，如果从上往下看他crush的女生，如果这个女生is taken了，我们就去看她男朋友能不能换一个（没错！明目张胆的NTR，给喜欢的对象的对象找对象），如果能，就让那个男的换一个，这个就归他了，如果换不了，就只能找下一个了；或者这个女生is single，就可以直接成了！
这样的话，整体的情侣就能达到最多的情况，我们画个图来表示一下，下面的黑线表示互相之间有crush，红线表示成了，绿线说明被绿了hh！
OK，这就是关于匈牙利算法的基本思路了，他的时间复杂度，在最坏最坏的情况下是O（nm）的，但一般都不会有这种情况，还是很快的！
代码：
include
define maxn 510
define maxm 100010
using namespace std;
int h[maxn],e[maxm],ne[maxm],idx;
int match[maxn];
int n1 , n2 ,m;
bool st[maxn];
void add(int a,int b){
e[idx] = b; ne[idx] = h[a] ; h[a] = idx++;
}
bool find(int x){
for(int i = h[x];i!=-1;i = ne[i]){
int j = e[i];
if(!st[j]){
st[j] = true;
if(match[j] == 0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n1 >> n2 >> m;
while (m — ){
int u,v;
cin >> u >> v;
add(u , v);
}
int res = 0;
for(int i = 1;i
Original: https://www.cnblogs.com/ZheyuHarry/p/16062382.html
Author: ZheyuHarry
Title: 匈牙利算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583620/
转载文章受原作者版权保护。转载请注明原作者出处！