KM算法是用来求完备匹配下的最大权匹配: 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接<Xi,Yj>有权Wij，求一种匹配使得所有Wij的和最大——-即最佳匹配。
记 L(x) 表示结点 x 的标记量，如果对于二部图中的任何边<x,y>，都有 L(x)+ L(y)>= Wx,y，我们称 L 为二部图的可行顶标。
设 G(V,E) 为二部图， G'(V,E’) 为二部图的子图。如果对于 G’ 中的任何边<x,y> 满足， L(x)+ L(y)== Wx,y，我们称 G'(V,E’) 为 G(V,E) 的等价子图。
定理一：设 L 是二部图 G 的可行顶标。若 L的等价子图 GL 有完美匹配 M，则 M 是 G 的最佳匹配。
由上述定理，我们可以通过来不断修改可行顶标，得到等价子图，从而求出最佳匹配。
基本概念
对于二分图,约定每个点都设有一个标号， 记lx[i]为X方点 i 的标号，ly[j]为Y方点 j 的标号。
可行点标：对于图中任意边（i，j，w）都有lx[i]+ly[j]>=W,则这一组点标是可行点标。
可行边：特别的，对于任意 lx[i]+ly[j]==W 的边（i，j，w）称为可行边。
有了以上概念，我们可以知道KM算法的核心思想就是，不断的修改某些点的标号(满足点标始终可行)，增加图中可行边数量，直到图中存在仅有可行边组成的完全匹配为止。
此时得到完全匹配匹配一定是最佳匹配：因为由可行点标的定义，图中任意一个完全匹配，其边权总和均不大于其相应点标号之和，而仅有可行边组成的完全匹配的边权总和等于其相应点的标号之和。
Kuhn－Munkras算法大致流程：
(1)初始化可行顶标的值；
(2)用匈牙利算法寻找完备匹配；
(3)若未找到完备匹配则修改可行顶标的值；
(4)重复(2)(3)直到找到相等子图的完备匹配为止；
KM算法及其具体过程
对于以上KM算法的大致步骤，我们在详细叙述它的具体步骤：
① 初始化可行顶标:
x[i]=max{e.W|e.x=i}；即每个X方点的初始标号为与这个X方点相关联的权值最大的边的权值。
ly[j]=0；即每个Y方点的初始标号为0。
这个初始点标显然是可行的，并且，与任意一个X方点关联的边中至少有一条可行边；
② 从每个X方点开始DFS增广。DFS增广的过程与最大匹配的Hungary算法基本相同，只是要注意两点：一是只找可行边，二是要把搜索过程中遍历到的X方的点全部记下来进行后面的修改；
③ 若增广成功，则从下一点继续增广。
④ 得到 d 值，修改可行线标后继续增广。
以上就是整个算法的全部步骤。
对于第二步，增广的结果有两种：若成功，则该点增广完成，进入下一个点的增广。若失败，则需要改变一些点的标号，使得图中可行边的数量增加。
方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，所有在增广轨中的Y方点的标号全部加上一个常数d。
则对于图中的任意一条边(i, j, W)（i为X方点，j为Y方点）：
<1>i和j都在增广轨中：此时边(i, j)的(lx[i]+ly[j])值不变，也就是这条边的可行性不变（原来是可行边则现在仍是，原来不是则现在仍不是）；
<2>i在增广轨中而j不在：此时边(i, j)的(lx[i]+ly[j])的值减少了d，也就是原来这条边不是可行边（否则j就会被遍历到了），而现在可能是；
<3>j在增广轨中而i不在：此时边(i, j)的(lx[i]+ly[j])的值增加了d，也就是原来这条边不是可行边（若这条边是可行边，则在遍历到j时会紧接着执行DFS(i)，此时i就会被遍历到），现在仍不是；
<4>i和j都不在增广轨中：此时边(i, j)的(lx[i]+ly[j])值不变，也就是这条边的可行性不变。
这样，在进行了这一步修改操作后，图中原来的可行边仍可行，而原来不可行的边现在则可能变为可行边。那么d的值应取多少？
显然，整个点标不能失去可行性，也就是对于上述的第<2>类边，其lx[i]+ly[j]>=W这一性质不能被改变，故取所有第<2>类边的(lx[i]+ly[j]-W)的最小值作为d值即可。这样一方面可以保证点标的可行性，另一方面，经过这一步后，图中至少会增加一条可行边。
算法改进
以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]n等于原值与 A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d。
【求二分图的最小权匹配】
只需把权值取反，变为负的，再用KM算出最大权匹配，取反则为其最小权匹配。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define _Clr(x, y) memset(x, y, sizeof(x)) 5 #define INF 0x3f3f3f3f 6 #define N 310 7 using namespace std; 8 9 int map[N][N], match[N]; 10 int lx[N], ly[N]; 11 int slack[N], n; 12 bool used_x[N], used_y[N]; 13 14 bool dfs(int x) 15 { 16 used_x[x] = true; 17 for(int i=1; i<=n; i++) 18 { 19 if(used_y[i]) continue; 20 int tp = lx[x]+ly[i]-map[x][i]; 21 if(tp==0) // 在相等子图中：<x, i>为可行边 22 { 23 used_y[i] = true; 24 if(match[i]==-1 || dfs(match[i])) 25 { 26 match[i] = x; 27 return true; 28 } 29 } 30 else 31 slack[i] = min(slack[i], tp); 32 } 33 return false; 34 } 35 36 int KM() 37 { 38 // 初始化可行项标 39 _Clr(ly, 0); 40 _Clr(match, -1); 41 for(int i=1, j=1; i<=n; i++) 42 for(j=1, lx[i]=-INF; j<=n; j++) 43 lx[i] = max(lx[i], map[i][j]); 44 45 for(int i=1; i<=n; i++) 46 { 47 _Clr(slack, INF); // 初始化Y方点的松弛量函数 48 while(1) 49 { 50 _Clr(used_x, 0); 51 _Clr(used_y, 0); 52 if(dfs(i)) break; // 找到增广路，找下一条。 53 54 // 获取d值:不在增广轨中的Y方的松弛量slack[]的最小值 55 int d = INF; 56 for(int j=1; j<=n; j++) 57 if(!used_y[j] && slack[j] < d) 58 d = slack[j]; 59 60 // 在增广轨中的 X 方点的lx[]减去d值 61 for(int j=1; j<=n; j++) 62 if(used_x[j]) lx[j] -= d; 63 64 // 在增广轨中的 Y 方点的ly[]加上d值， 65 // 同时不再增广轨中的 Y 方点松弛量减去d值 66 for(int j=1; j<=n; j++) 67 if(!used_y[j]) 68 slack[j] -= d; 69 else ly[j] += d; 70 } 71 } 72 int ans=0; 73 for(int i=1; i<=n; i++) 74 if(match[i] > -1) ans += map[match[i]][i]; 75 return ans; 76 } 77 78 int main() 79 { 80 while(~scanf("%d", &n)) 81 { 82 for(int i=1; i<=n; i++) 83 for(int j=1; j<=n; j++) 84 scanf("%d", &map[i][j]); 85 printf("%d ", KM()); 86 } 87 return 0; 88 }
View Code
题目大意：
现 在有1所学校，N个学生,M个公寓，还有一个R值，代表学生对该公寓的满意度，数越高表示越喜欢住在该所公寓，0表示不喜欢也不讨厌，如果为负数则代表不 喜欢住，也不能住。现在校长想让所有学生的满意度最高，而且学生跟公寓是一一对应的，另外，学生也不能入住那些没对公寓进行评价的。
求出最大值。
这个有几个需要的注意的地方：
1. N，M可能不相等，所以要得到N的完备匹配，N<=M才行。
2. 图中有负权值的边。
3. 判断完备匹配是否存在。
对于第二点，因为边为负表示不会入住，所以我们可以初始化mat[][]为-INF。然后在输入边的时候忽略掉负边。在匹配的时候统计合法匹配的个数并忽略掉初始边即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define _Clr(x, y) memset(x, y, sizeof(x)) 5 #define INF 0xfffffff 6 #define N 520 7 using namespace std; 8 9 int mat[N][N], match[N]; 10 int slack[N], n, m; 11 int lx[N], ly[N]; 12 bool used_x[N], used_y[N]; 13 14 bool dfs(int x) 15 { 16 used_x[x] = true; 17 for(int i=0; i<m; i++) 18 { 19 if(used_y[i]) continue; 20 int t = lx[x] + ly[i] - mat[x][i]; 21 if(t==0) 22 { 23 used_y[i] = true; 24 if(match[i]==-1 || dfs(match[i])) 25 { 26 match[i] = x; 27 return true; 28 } 29 } 30 else slack[i] = min(slack[i], t); 31 } 32 return false; 33 } 34 35 void KM() 36 { 37 _Clr(ly, 0); 38 _Clr(match, -1); 39 for(int i=0, j; i<n; i++) 40 for(lx[i]=-INF,j=0; j<m; j++) 41 lx[i] = max(lx[i], mat[i][j]); 42 for(int x=0; x<n; x++) 43 { 44 for(int i=0; i<m; i++) slack[i] = INF; 45 while(1) 46 { 47 _Clr(used_x, 0); 48 _Clr(used_y, 0); 49 if(dfs(x)) break; 50 51 int d = INF; 52 for(int i=0; i<m; i++) 53 if(!used_y[i] && slack[i] < d) 54 d = slack[i]; 55 if(d==INF) 56 { 57 puts("-1"); 58 return; 59 } 60 for(int i=0; i<n; i++) 61 if(used_x[i]) lx[i] -= d; 62 for(int i=0; i<m; i++) 63 if(used_y[i]) ly[i] += d; 64 else slack[i] -= d; 65 } 66 } 67 int cnt=0, ans=0; 68 for(int i=0;i<m; i++) 69 if(match[i]!=-1 && mat[match[i]][i]!=-INF) 70 ans += mat[match[i]][i], cnt++; 71 if(cnt==n) 72 printf("%d ", ans); 73 else puts("-1"); 74 } 75 int main() 76 { 77 int s, r, v, k; 78 int lop=0; 79 while(~scanf("%d%d%d", &n, &m, &k)) 80 { 81 for(int i=0; i<n; i++) 82 for(int j=0; j<m; j++) mat[i][j] = -INF; 83 for(int i=0; i<k; i++) 84 { 85 scanf("%d%d%d", &s, &r, &v); 86 if(v >= 0) 87 mat[s][r] = v; 88 } 89 printf("Case %d: ", ++lop); 90 if(n>m) 91 puts("-1"); 92 else 93 KM(); 94 } 95 return 0; 96 }
View Code