匈牙利算法

本文主要是介绍匈牙利算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这就是NTR算法 ？？ 渣男渣女算法 ？？

接下来要介绍的NTR算法，啊呸，不对不对，匈牙利算法，是一种确定二分图的最大匹配数量的一种非常高效的算法；

我们先介绍一下二分图的匹配以及最大匹配：

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

换言之，二分图的匹配就是点与点之间一 一对应，最大匹配就是一 一对应的个数能有多大；

接下来，我们将介绍y总的奇妙比喻：我们把不同点集之间的匹配比作男女生找对象，就假设左边是男生，右边是女生好了，如果两者之间有一条边，就说明这俩互相有crush，能撮合到一起；

我们的角色就是月老，我们想让尽可能多的情侣出现，所以我们遍历男生，这个男生的所有边都是可能是他的女朋友，如果从上往下看他crush的女生，如果这个女生is taken了，我们就去看她男朋友能不能换一个（没错！明目张胆的NTR，给喜欢的对象的对象找对象），如果能，就让那个男的换一个，这个就归他了，如果换不了，就只能找下一个了；或者这个女生is single，就可以直接成了！

这样的话，整体的情侣就能达到最多的情况，我们画个图来表示一下，下面的黑线表示互相之间有crush，红线表示成了，绿线说明被绿了hh！

OK，这就是关于匈牙利算法的基本思路了，他的时间复杂度，在最坏最坏的情况下是O（nm）的，但一般都不会有这种情况，还是很快的！

代码：

#include<bits/stdc++.h>
#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<=n1;i++){
memset(st, false, sizeof st);
if(find(i)) res++;
}
cout << res << '\n';
return 0;
}

这篇关于匈牙利算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！