二分图匹配——匈牙利算法板子

本文主要是介绍二分图匹配——匈牙利算法板子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

7
1 5
2 5
5 1
5 3
3 6
7 4
4 8

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
const int MAXN=555;
const int n=100;vector<int> g[MAXN];
int form[MAXN],tot;
bool use[MAXN];bool match(int x){for(int i=0;i<g[x].size();i++){if(!use[g[x][i]]){use[g[x][i]]=true;if(form[g[x][i]]==-1 || match(form[g[x][i]])){form[g[x][i]]=x;return x;}}}}int hungary(){tot=0;memset(form,255,sizeof(form));for(int i=1;i<=n;i++){memset(use,0,sizeof(use));if(match(i))++tot;}return tot;
}int main()
{int N;cin>>N;int a,b;int ans=0;for(int i=1;i<=N;i++){cin>>a>>b;g[a].push_back(b);}ans=hungary();cout<<ans<<endl;
}

 

这篇关于二分图匹配——匈牙利算法板子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---