二分图最大匹配
匈牙利算法
匈牙利算法用来求解二分图的最大匹配.
对于一个匹配为 的二分图 , 顶点集被划分为 , 若 满足某个以 为端点的边在 中, 则称 被匹配, 否则称其未被匹配; 若 则称边 为匹配边, 否则称为未匹配边.
定义交替路如下:
定义1 (交替路) 交替路是一段 path , 满足
未被匹配且路径上的边是未匹配边和匹配边交错的, 即 .
在交替路的基础上给出增广路的定义:
定义2 (增广路) 增广路是一条交替路,
满足其终点未被匹配.
显然增广路中, 未匹配边比匹配边多一条,
于是可以将匹配边变成未匹配边,
而未匹配边变成匹配边(即匹配边和未匹配边进行对调),
这不会违反匹配的要求, 于是得到新的匹配 , 且满足 ,
这样的一次操作使匹配的条数增加了 .
于是自然就有下面的思路:
通过搜索不断地发现增广路, 每次找到一条增广路就做如上述的操作,
直到找不到增广路为止.
每个未被匹配的点只需要枚举一次.
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
const int maxn2=5e4;
typedef struct _edge{
int from,to;
_edge(int _from, int _to):from(_from),to(_to){}
}Edge;
vector<Edge>edge;
vector<int> g[2*maxn+5];
int mate[2*maxn+5];
int check[2*maxn+5];
int n,m,e;
bool dfs(int s){
for(vector<int>::iterator it=g[s].begin();it!=g[s].end();++it){
int v=edge[*it].to;
if(!check[v]){
check[v]=1;
if(mate[v]==-1||dfs(mate[v])){
mate[v]=s;
mate[s]=v;
return true;
}
}
}
return false;
}
int matching(){
memset(mate,-1,sizeof(mate));
int ans=0;
for(int i=1;i<=n;i++){
if(mate[i]==-1){
memset(check,0,sizeof(check));
if(dfs(i))ans++;
}
}
return ans;
}
int isv[2*maxn+5][2*maxn+5];
int main(){
cin>>n>>m>>e;
int a,b;
int cnt=0;
for(int i=0;i<e;i++){
cin>>a>>b;
if(!isv[a][b+n]){
edge.push_back(Edge(a,b+n));
g[a].push_back(cnt++);
isv[a][b+n]=isv[b+n][a]=1;
}
}
cout<<matching();
return 0;
}
|
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=500;
const int maxn2=5e4;
typedef struct _edge{
int from,to;
_edge(int _from, int _to):from(_from),to(_to){}
}Edge;
vector<Edge>edge;
vector<int> g[2*maxn+5];
int mate[2*maxn+5];
int pre[2*maxn+5];
int check[2*maxn+5];
queue<int> Q;
int matching(int n){
int ans=0;
memset(mate,-1,sizeof(mate));
memset(check,-1,sizeof(check));
for(int i=1;i<=n;i++){
if(mate[i]==-1){
while(!Q.empty()) Q.pop();
memset(pre,0,sizeof(pre));
Q.push(i);
pre[i]=-1;
int flag=0;
while (!Q.empty()&&!flag)
{
int v=Q.front(); Q.pop();
for(vector<int>::iterator it=g[v].begin();it!=g[v].end()&&!flag;++it){
int u=edge[*it].to;
if(check[u]!=i){
check[u]=i;
Q.push(mate[u]);
if(mate[u]>=0){
pre[u]=v;
pre[mate[u]]=u;
}
else{
pre[u]=v;
flag=1;
int x=u;
while(x!=-1){
int y=pre[x];
mate[x]=y;
mate[y]=x;
x=pre[y];
}
}
}
}
}
if(mate[i]!=-1) ans++;
}
}
return ans;
}
int isv[2*maxn+5][2*maxn+5];
int main(){
int n,m,e;
cin>>n>>m>>e;
int a,b;
int cnt=0;
for(int i=0;i<e;i++){
cin>>a>>b;
if(!isv[a][b+n]){
edge.push_back(Edge(a,b+n));
g[a].push_back(cnt++);
isv[a][b+n]=isv[b+n][a]=1;
}
}
cout<<matching(n);
return 0;
}
|
用BFS实现时, 需要注意在将点待搜索点放入队列时, 需要放的点是当前点
的邻接点 的配偶, 这样相当于一次搜索跳了两步,
包括非匹配边 和匹配边 ,
效率比深度一次只增加一层要高一些并且不用额外判断是否满足交替路的条件.
和网络流的FF算法和EK算法一样, 使用 BFS 的匈牙利算法要比使用 DFS
的效率高一些(稀疏图尤甚), 虽然时间复杂度都为 . (枚举 个点, 每个点找增广路需要 的时间.)
转化为网络流
一般图最大匹配
