题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2255
解题思路：
了解km算法以后，就可以直接套用km算法，km算法：完备匹配下的最大权匹配，
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 #define maxn 310 8 #define INF 0x3f3f3f3f 9 int map[maxn][maxn], used[maxn], s[maxn], n, m; 10 int lx[maxn], ly[maxn], visx[maxn], visy[maxn]; 11 12 int find (int x) 13 {//匈牙利算法，增广路 14 visx[x] = 1; 15 for (int i=1; i<=n; i++) 16 { 17 if (!visy[i] && lx[x] + ly[i] == map[x][i]) 18 { 19 visy[i] = 1; 20 if (!used[i] || find(used[i])) 21 { 22 used[i] = x; 23 return 1; 24 } 25 } 26 else 27 s[i] = min (s[i], lx[x]+ly[i]-map[x][i]); 28 } 29 return 0; 30 } 31 32 int KM () 33 { 34 memset (lx, 0, sizeof(lx)); 35 memset (ly, 0, sizeof(ly)); 36 memset (used, 0, sizeof(used)); 37 for (int i=1; i<=n; i++) 38 for (int j=1; j<=n; j++) 39 lx[i] = max (lx[i], map[i][j]); 40 for (int i=1; i<=n; i++) 41 { 42 for (int j=1; j<=n; j++) 43 s[j] = INF; 44 45 while (1) 46 { 47 memset (visx, 0, sizeof(visx)); 48 memset (visy, 0, sizeof(visy)); 49 50 if (find (i)) 51 break; 52 int num = INF; 53 for (int j=1; j<=n; j++) 54 if (!visy[j]) 55 num = min (num, s[j]); 56 for (int j=1; j<=n; j++) 57 { 58 if (visx[j]) 59 lx[j] -= num; 60 if (visy[j]) 61 ly[j] += num; 62 else 63 s[j] -= num; 64 } 65 } 66 } 67 int res = 0; 68 for (int j=1; j<=n; j++) 69 res += map[used[j]][j]; 70 return res; 71 } 72 int main () 73 { 74 while (scanf ("%d", &n) != EOF) 75 { 76 for (int i=1; i<=n; i++) 77 for (int j=1; j<=n; j++) 78 scanf ("%d", &map[i][j]); 79 printf ("%d ", KM()); 80 } 81 return 0; 82 }