今天分享的是匈牙利算法…
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
我觉得这个博主讲的挺生动形象的….
https://blog.csdn.net/dark_scope/article/details/8880547
过山车
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2063
匈牙利算法经典入门题
题意： 尽可能地组成最多的CP。具体想法可以看上文分享的那位博主的博客。（图文并茂）
下面是AC代码: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
using namespace std;
int K,M,N;
bool CP[1000+5][1000+5]; //记录女生u是否愿意跟男生v组成CP
int boy[1000+5]; //记录男生的对象是哪位女生
bool used[1000+5]; //记录是否被访问过
bool fun(int x){
for(int i=1;i<=N;i++){
if(CP[x][i]==true&&used[i]==false){ //可以组成CP且 该男生没有被访问过
used[i]=1;
if(boy[i]==0||fun(boy[i])){ //该男生还没组成CP，或者让原先跟这位男生组CP的女生去找其他男生组CP
boy[i]=x;
return true;
}
}
}
return false;
}
int main()
{
int u,v;
while(scanf("%d",&K)!=EOF){
int ans=0;
if(K==0)
break;
scanf("%d%d",&M,&N);
memset(CP,0,sizeof(CP));
memset(boy,0,sizeof(boy));
for(int i=0;i<K;i++){
scanf("%d%d",&u,&v);
CP[u][v]=1;
}
for(int i=1;i<=M;i++){
memset(used,0,sizeof(used)); //每次都是尝试让当前的女生去和男生组CP，所以需要重置used数组
if(fun(i))
ans++;
}
printf("%d\n",ans);
}
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
27bool CP[MAX][MAX];
bool used[MAX];
int linked[MAX];
bool fun(int x){
int i
for (i=1;i<=N;i++){
if (CP[x][i]==true && used[i]==false)
{
used[i]=1;
if (linked[i]==0 || fun(linked[i])) {
linked[j]=x;
return true;
}
}
}
return false;
}
int hungary(){
int ans=0;
memset(linked,0,sizeof(linked));
for(int i=1;i<=M;i++){
memset(used,0,sizeof(used));
if(fun(i))
ans++;
}
}
关于匈牙利算法，不能一见到二分图匹配，上来就匈牙利，不然很容易TLE的，毕竟如果是最坏情况的话，该算法是的复杂度高达$O（M*N^2）$