KM算法模板

大白书P248有证明,此处贴出两种复杂度的方案，
n^4
大白书P350
n^3
 1 #include <algorithm>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <cstdio>
 5 using namespace std;
 6 /* KM算法
 7 * 复杂度O(nx*nx*ny)
 8 * 求最大权匹配
 9 * 若求最小权匹配，可将权值取相反数，结果取相反数
10 * 点的编号从0开始
11 */
12 const int N = 310;
13 const int INF = 0x3f3f3f3f;
14 int nx,ny; //两边的点数
15 int W[N][N]; //二分图描述
16 int Left[N],Lx[N],Ly[N]; //y中各点匹配状态， x,y中的点标号
17 int slack[N];
18 bool S[N],T[N];
19 bool DFS(int x) {
20     S[x] = true;
21     for(int y = 0; y < ny; y++){
22         if(T[y]) continue;
23         int tmp = Lx[x] + Ly[y] - W[x][y];
24         if(tmp == 0){
25             T[y] = true;
26             if(Left[y] == -1 || DFS(Left[y])){
27                 Left[y] = x;
28                 return true;
29             }
30         }
31         else if(slack[y] > tmp)
32         slack[y] = tmp;
33     }
34     return false;
35 }
36 int KM(){
37     memset(Left, -1, sizeof(Left));
38     memset(Ly,0, sizeof(Ly));
39     for(int i = 0;i < nx;i++){
40     Lx[i] = -INF;
41     for(int j = 0;j < ny;j++)
42         if(W[i][j] > Lx[i])
43             Lx[i] = W[i][j];
44     }
45     for(int x = 0;x < nx;x++){
46         for(int i = 0;i < ny;i++)
47             slack[i] = INF;
48         while(true){
49             memset(S, false, sizeof(S));
50             memset(T, false, sizeof(T));
51             if(DFS(x)) break;
52             int d = INF;
53             for(int i = 0;i < ny;i++)
54             if(!T[i] && d > slack[i])
55             d = slack[i];
56             for(int i = 0;i < nx;i++)
57                 if(S[i])
58             Lx[i] -= d;
59             for(int i = 0;i < ny;i++){
60                 if(T[i])Ly[i] += d;
61                 else slack[i] -= d;
62             }
63         }
64     }
65     int res = 0;
66     for(int i = 0;i < ny;i++)
67         if(Left[i] != -1)
68             res += W[Left[i]][i];
69     return res;
70 }
71 //HDU 2255
72 int main()
73 {
74     int n;
75     while(scanf("%d",&n) == 1){
76         for(int i = 0;i < n;i++)
77             for(int j = 0;j < n;j++)
78            scanf("%d",&W[i][j]);
79         nx = ny = n;
80         printf("%d
",KM());
81     }
82     return 0;
83 }