二分图最大权完美匹配KM算法

KM算法二分图

KM求得二分图与普通二分图的不同之处在于：此二分图的每条边（男生女生）上都附了权值（好感度）。然后，求怎样完美匹配使得权值之和最大。

这，不止一般的麻烦啊。

可以通过一个期望值来求。

大致思路就是：

每个男生女生都有期望值，男生一开始全部为0，女生一开始则是可能的最大值。

匹配的条件为男生的期望值加上女生的期望值等于他们之间的权值（好感度）。

每次如果不能匹配，就降一下参加匹配的女生的期望值，加一下参加匹配的男生的期望值。

基本思路就这样，具体参考别人的一篇博客。

代码也是人家的。。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int MAXN=305;
 6 const int INF=0x3f3f3f3f;
 7 int love[MAXN][MAXN];//记录每个妹子和每个男生的好感度
 8 int ex_girl[MAXN];//每个妹子的期望值
 9 int ex_boy[MAXN];//每个男生的期望值
10 bool vis_girl[MAXN];//记录每一轮匹配匹配过的女生
11 bool vis_boy[MAXN];//记录每一轮匹配匹配过的男生
12 int match[MAXN];//记录每个男生匹配到的妹子 如果没有则为-1
13 int slack[MAXN];//记录每个汉子如果能被妹子倾心最少还需要多少期望值
14 int N;
15 bool dfs(int girl){
16     vis_girl[girl]=true;
17     for(int boy=0;boy<N;++boy) {
18         if(vis_boy[boy])
19             continue;//每一轮匹配 每个男生只尝试一次
20         int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];
21         if(gap==0){//如果符合要求
22             vis_boy[boy]=true;
23             if(match[boy]==-1||dfs(match[boy])){//找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
24                 match[boy]=girl;
25                 return true;
26             }
27         }
28         else
29             slack[boy]=min(slack[boy],gap);//slack可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值
30     }
31     return false;
32 }
33 int KM(){
34     memset(match,-1,sizeof match);//初始每个男生都没有匹配的女生
35     memset(ex_boy,0,sizeof ex_boy);//初始每个男生的期望值为0
36     //每个女生的初始期望值是与她相连的男生最大的好感度
37     for(int i=0;i<N;++i){
38         ex_girl[i]=love[i][0];
39         for(int j=1;j<N;++j)
40             ex_girl[i]=max(ex_girl[i],love[i][j]);
41     }
42     //尝试为每一个女生解决归宿问题
43     for(int ii=0;ii<N;++ii){
44         fill(slack,slack+N,INF);//因为要取最小值 初始化为无穷大
45         while(1){
46             //为每个女生解决归宿问题的方法是：如果找不到就降低期望值，直到找到为止
47             //记录每轮匹配中男生女生是否被尝试匹配过
48             memset(vis_girl,false,sizeof vis_girl);
49             memset(vis_boy,false,sizeof vis_boy);
50             if(dfs(ii))
51                 break;//找到归宿 退出
52             //如果不能找到 就降低期望值
53             int d=INF;//最小可降低的期望值
54             for(int j1=0;j1<N;++j1)
55                 if(!vis_boy[j1])
56                     d=min(d,slack[j1]);
57             for(int j2=0;j2<N;++j2){
58                 //所有访问过的女生降低期望值
59                 if(vis_girl[j2])
60                     ex_girl[j2]-=d;
61                 //所有访问过的男生增加期望值
62                 if(vis_boy[j2])
63                     ex_boy[j2]+=d;
64                 //没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
65                 else
66                     slack[j2]-=d;
67             }
68         }
69     }
70     //匹配完成 求出所有配对的好感度的和
71     int res=0;
72     for(int iii=0;iii<N;++iii)
73         res+=love[match[iii]][iii];
74     return res;
75 }
76 int main(){
77     scanf("%d",&N);
78     for(int i=0;i<N;++i)
79         for(int j=0;j<N;++j)
80             scanf("%d",&love[i][j]);
81     printf("%d
",KM());
82     return 0;
83 }

View Code

具体实现过程还是得自己理解，实在不行就自己调试几遍，提供一个数据：

直接就是那篇博客的图。