km算法（求二分圖帶權的最大比對）

1，如果二分圖不是完全二分圖，我們通過添加無用路徑（最大比對中，路徑權值為0）和頂點使之成為完全二分圖；

2，使用KM算法求解，KM算法核心需要了解feasible vertex labeling和equality subgraph概念，在equality subgraph中尋找最大比對（采用匈牙利算法），如果最大比對正好為完全比對，根據KM理論，這個完全比對就是帶權值的最大比對；如果在目前的equality subgraph擷取的最大比對不是完全比對，我們通過KM算法中提供的修改label方法，增加新的y點，得到新的equality subgraph，再繼續在新的subgraph尋找最大比對，如此循環。

代碼如下：

[cpp]  view plain copy

1. #include <cstdio>  
2. #include <memory.h>  
3. #include <algorithm>    // 使用其中的 min 函數  
4. using namespace std;  
5. const int MAX = 1024;  
6. int n; // X 的大小  
7. int weight[MAX][MAX]; // X 到 Y 的映射（權重）  
8. int lx[MAX], ly[MAX]; // 标号  
9. bool sx[MAX], sy[MAX]; // 是否被搜尋過  
10. int match[MAX]; // Y(i) 與 X(match [i]) 比對  
11. // 初始化權重  
12. void init(int size);  
13. // 從 X(u) 尋找增廣道路，找到則傳回 true  
14. bool path(int u);  
15. // 參數 maxsum 為 true ，傳回最大權比對，否則最小權比對  
16. int bestmatch(bool maxsum = true);  
17. void init(int size)  
18. {  
19.     // 根據實際情況，添加代碼以初始化  
20.     n = size;  
21.     for (int i = 0; i < n; i++)  
22.         for (int j = 0; j < n; j++)  
23.             scanf("%d", &weight[i][j]);  
24. }  
25. bool path(int u)  
26. {  
27.     sx[u] = true;  
28.     for (int v = 0; v < n; v++)  
29.         if (!sy[v] && lx[u] + ly[v] == weight[u][v])  
30.         {  
31.             sy[v] = true;  
32.             if (match[v] == -1 || path(match[v]))  
33.             {  
34.                 match[v] = u;  
35.                 return true;  
36.             }  
37.         }  
38.     return false;  
39. }  
40. int bestmatch(bool maxsum)  
41. {  
42.     int i, j;  
43.     if (!maxsum)  
44.     {  
45.         for (i = 0; i < n; i++)  
46.             for (j = 0; j < n; j++)  
47.                 weight[i][j] = -weight[i][j];  
48.     }  
49.     // 初始化标号  
50.     for (i = 0; i < n; i++)  
51.     {  
52.         lx[i] = -0x1FFFFFFF;  
53.         ly[i] = 0;  
54.         for (j = 0; j < n; j++)  
55.             if (lx[i] < weight[i][j])  
56.                 lx[i] = weight[i][j];  
57.     }  
58.     memset(match, -1, sizeof(match));  
59.     for (int u = 0; u < n; u++)  
60.         while (1)  
61.         {  
62.             memset(sx, 0, sizeof(sx));  
63.             memset(sy, 0, sizeof(sy));  
64.             if (path(u))    //一直尋找增廣路徑，直到子圖中沒有增廣路徑，我們通過修改label來增加新的點，增加的點必為y  
65.                 break;  
66.             // 修改标号  
67.             int dx = 0x7FFFFFFF;  
68.             for (i = 0; i < n; i++)  
69.                 if (sx[i])  
70.                     for (j = 0; j < n; j++)  
71.                         if (!sy[j])  
72.                             dx = min(lx[i] + ly[j] - weight[i][j], dx); //找到松弛變量最小的點  
73.             for (i = 0; i < n; i++)  
74.             {  
75.                 if (sx[i])  
76.                     lx[i] -= dx;  
77.                 if (sy[i])  
78.                     ly[i] += dx;  
79.             }  
80.         }  
81.     int sum = 0;  
82.     for (i = 0; i < n; i++)  
83.         sum += weight[match[i]][i];  
84.     if (!maxsum)  
85.     {  
86.         sum = -sum;  
87.         for (i = 0; i < n; i++)  
88.             for (j = 0; j < n; j++)  
89.                 weight[i][j] = -weight[i][j]; // 如果需要保持 weight [ ] [ ] 原來的值，這裡需要将其還原  
90.     }  
91.     return sum;  
92. }  
93. int main()  
94. {  
95.     int n;  
96.     scanf("%d", &n);  
97.     init(n);  
98.     int cost = bestmatch(true);  
99.     printf("%d ", cost);  
100.     for (int i = 0; i < n; i++)  
101.     {  
102.         printf("Y %d -> X %d ", i, match[i]);  
103.     }  
104.     return 0;  
105. }  

附帶poj2195解法：

[cpp]  view plain copy

1. #include <cstdio>  
2. #include <cstdlib>  
3. #include <string.h>  
4. #include <algorithm>  
5. #include <cmath>  
6. using namespace std;  
7. #define MAX 200  
8. typedef struct GRID  
9. {  
10.     int x;  
11.     int y;  
12. }grid, pgrid;  
13. grid M[MAX], H[MAX];  
14. int n; // X 的大小  
15. int weight[MAX][MAX]; // X 到 Y 的映射（權重）  
16. int lx[MAX], ly[MAX]; // 标号  
17. bool sx[MAX], sy[MAX]; // 是否被搜尋過  
18. int match[MAX]; // Y(i) 與 X(match [i]) 比對  
19. bool path(int u)  
20. {  
21.     sx[u] = true;  
22.     for (int v = 0; v < n; v++)  
23.         if (!sy[v] && lx[u] + ly[v] == weight[u][v])  
24.         {  
25.             sy[v] = true;  
26.             if (match[v] == -1 || path(match[v]))  
27.             {  
28.                 match[v] = u;  
29.                 return true;  
30.             }  
31.         }  
32.     return false;  
33. }  
34. int bestmatch(bool maxsum)  
35. {  
36.     int i, j;  
37.     if (!maxsum)  
38.     {  
39.         for (i = 0; i < n; i++)  
40.             for (j = 0; j < n; j++)  
41.                 weight[i][j] = -weight[i][j];  
42.     }  
43.     // 初始化标号  
44.     for (i = 0; i < n; i++)  
45.     {  
46.         lx[i] = -0x1FFFFFFF;  
47.         ly[i] = 0;  
48.         for (j = 0; j < n; j++)  
49.             if (lx[i] < weight[i][j])  
50.                 lx[i] = weight[i][j];  
51.     }  
52.     memset(match, -1, sizeof(match));  
53.     for (int u = 0; u < n; u++)  
54.         while (1)  
55.         {  
56.             memset(sx, 0, sizeof(sx));  
57.             memset(sy, 0, sizeof(sy));  
58.             if (path(u))    //一直尋找增廣路徑，直到子圖中沒有增廣路徑，我們通過修改label來增加新的點，增加的點必為y  
59.                 break;  
60.             // 修改标号  
61.             int dx = 0x7FFFFFFF;  
62.             for (i = 0; i < n; i++)  
63.                 if (sx[i])  
64.                     for (j = 0; j < n; j++)  
65.                         if (!sy[j])  
66.                             dx = min(lx[i] + ly[j] - weight[i][j], dx); //找到松弛變量最小的點  
67.             for (i = 0; i < n; i++)  
68.             {  
69.                 if (sx[i])  
70.                     lx[i] -= dx;  
71.                 if (sy[i])  
72.                     ly[i] += dx;  
73.             }  
74.         }  
75.     int sum = 0;  
76.     for (i = 0; i < n; i++)  
77.         sum += weight[match[i]][i];  
78.     if (!maxsum)  
79.     {  
80.         sum = -sum;  
81.         for (i = 0; i < n; i++)  
82.             for (j = 0; j < n; j++)  
83.                 weight[i][j] = -weight[i][j]; // 如果需要保持 weight [ ] [ ] 原來的值，這裡需要将其還原  
84.     }  
85.     return sum;  
86. }  
87. int main()  
88. {  
89.     int row, col;  
90.     int i, j;  
91.     int ch;  
92.     int mCount, hCount;  
93.     while(1)  
94.     {  
95.         scanf("%d %d", &row, &col);  
96.         getchar();  
97.         if(row == 0 && col == 0)  
98.             break;  
99.         mCount = 0;  
100.         hCount = 0;  
101.         for(i = 0; i < row ; i++)  
102.         {  
103.             for(j = 0; j < col; j++)  
104.             {  
105.                 ch = getchar();  
106.                 if(ch == 'm')  
107.                 {  
108.                     M[mCount].x = i;  
109.                     M[mCount].y = j;  
110.                     mCount++;  
111.                 }  
112.                 else  
113.                     if(ch == 'H')  
114.                     {  
115.                         H[hCount].x = i;  
116.                         H[hCount].y = j;  
117.                         hCount++;  
118.                     }  
119.             }  
120.             getchar();  
121.         }  
122.         n = mCount;  
123.         for(i = 0 ; i < n; i++)  
124.             for(j = 0; j < n; j++)  
125.             {  
126.                 weight[i][j] = abs(M[i].x - H[j].x) + abs(M[i].y - H[j].y);  
127.             }  
128.         printf("%d\n", bestmatch(false));  
129.     }  
130.     return 0;  
131. }