匈牙利算法
xzyxzy
2018-02-03 21:52:30
#**匈牙利算法**
##更好阅读体验：https://www.zybuluo.com/xzyxzy/note/980353
---
###**一、基本内容**
博客：http://www.renfei.org/blog/bipartite-matching.html
主要在于增广路的理解
###**二、实现**
一般是E遍搜索(DFS)，一次搜索大约是V的复杂度，总共$O(E⋅V)$(点数乘边数)
###**三、适用范围**
二分图匹配问题
然后如果不是二分图(奇环)的最大匹配要用[带花树][1]
###**四、题目**
####**1、练基础**
P3386 【模板】二分图匹配 https://www.luogu.org/problemnew/show/P3386
P1129 [ZJOI2007]矩阵游戏 https://www.luogu.org/problemnew/show/P1129
P1894 [USACO4.2]完美的牛栏 https://www.luogu.org/problemnew/show/P1894
P2756 飞行员配对方案问题 https://www.luogu.org/problemnew/show/P2756
####**2、刷提高**
P1402 酒店之王 https://www.luogu.org/problemnew/show/P1402
P2055 [ZJOI2009]假期的宿舍 https://www.luogu.org/problemnew/show/P2055
P2763 试题库问题 https://daniu.luogu.org/problemnew/show/2763
###**五、做题经验**
####**1、每次寻找增广路都要记得初始化used数组**
```cpp
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
ans+=DFS(i);
}
```
这是第二次敲模板时忽略的问题
####**2、想清楚题目是否可以用二分图，怎么用**
对于酒店之王，要用两个二分图而且不能合并，合并会使得匹配数增加
###**附录**
```cpp
//P3386模板
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=1001;
bool used[N],f[N][N];
int match[N],n,m,e,ans=0;
bool DFS(int pos)
{
for(int i=1;i<=m;i++)
{
if(used[i]||!f[pos][i])continue;
used[i]=1;
if(!match[i]||DFS(match[i]))
{
match[i]=pos;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&e);
for(int i=1;i<=e;i++)
{
int x,y;scanf("%d%d",&x,&y);
if(x<=n&&y<=m)f[x][y]=1;
}
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
ans+=DFS(i);
}
printf("%d\n",ans);
return 0;
}
```
tags：算法
[1]: http://www.cnblogs.com/y-clever/p/8084738.html