【二分图匹配】最大匹配-匈牙利算法BFS DFS写法

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

搞了两节课终于搞懂了ORZ

这个讲解得很详细http://blog.csdn.net/pi9nc/article/details/11848327  

注意：每次找增广路之前都要初始化

           BFS写法要多加一个Prev数组保存这个点从哪个点来（同侧）

          如果给出的两个点集各自序号都是1~n的： 对于DFS写法 因为其隐形地调用了一个栈 只要开一个Matchine数组记录一侧的匹配；

                                                                                      对于BFS写法  必须开两个Matchine数组

          如果给出的点集只有一组序号= =就只要开一个了233  如果两个集合序号互有穿插，可以都下去找一遍，匹配数/2 

         比如下面HDU2444

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 210
bool flag;
int i,n,m,color[maxn],map[maxn][maxn],matchine[maxn],mark[maxn],ans;void dfs(int now,int x){for (int i=1;i<=n;i++){if (map[now][i]){if (!color[i]) {color[i]=3-x;dfs(i,3-x);}else if (color[i]==x) {flag=false;return;}if (flag==false) return;}}
}bool check(){memset(color,0,sizeof(color));color[1]=1;flag=true;dfs(1,1);return flag;
}bool find(int now){  for (int j=1;j<=n;j++)if (map[now][j] && !mark[j]){m

这篇关于【二分图匹配】最大匹配-匈牙利算法BFS DFS写法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---