匈牙利算法 | Kyons'Blog 




 
 
 
 



 
 



匈牙利算法

参拜大佬%%%

二分图

定义

  严格的定义请参加百度百科什么的.这里简单讲一下我的理解.就是给你一个图,有n个点.你可以按照边的关系,将这n个点分成两部分,而且这两部分之间有边相连.但是每一部分里面的点互不相连.
  如图1,左右两部分的点随意相连,但是每部分里的每一个点互不相连.
1

匹配

  首先是极大匹配(Maximal Matching),是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
  而最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
  如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
  求二分图匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm).
  当然本蒟蒻还没有学最大流

匈牙利算法

  我们来看图二,可以知道了这个二分图各点之间的联系.那么该算法如何实现最大匹配呢.
2
  根据字典序,显然易见,我们可以知道,A->E.
  随后,我们看B点,它要连E,但是E被占用了,我们该怎么办?我们把A->E之间的边暂时去掉,变成黄色,然后让B->E链接,但是A不能没有,于是这里从A再走,E不行,但是有个F.所以A->F.
3
4
  于是C->G也按此法加上,轮到D,我们发现G已经被连了.怎么办?将C->G的边暂时去掉.再从C走,看是否可以找别的边.但是我们发现,C只有到G的一条边.所以C->G保留,D只能孤立一人,我们无能为力.

核心代码

1
2
3
4
5
6
7
8
9
10
bool find(int x)
{
for (int i = 1; i <= ny; i++)
if (!used[i] && m[x][i]) { //used[]指的是,这个点是否被处理过.m[][]是指两者之间是否相连
used[i] = 1;
if (!y[i] || find(y[i])) //如果这个点没有被链接,或者可以调整
return y[i] = x;
}
return 0;
}

完整代码

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
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<string>
#include<math.h>
#include<map>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
#define maxn 10000
using namespace std;

typedef long long ll;
int m[maxn][maxn], used[maxn],y[maxn],nx, ny;
bool find(int x)
{
for (int i = 1; i <= ny; i++)
if (!used[i] && m[x][i]) {
used[i] = 1;
if (!y[i] || find(y[i]))
return y[i] = x;
}
return 0;
}
int main()
{
int ans = 0,d;
cin >> nx >> ny>>d;
for (int i = 0; i < d; i++) {
int x, y;
cin >> x >> y;
m[x][y] = 1;
}
for (int i = 1; i <= nx; i++) {
memset(used, 0, sizeof(used));
if (find(i))
ans++;
}
for (int i = 1; i <= ny; i++)
cout << y[i] << ':' << i << endl;
cout << ans << endl;
return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载