这题一打眼是最大费用最大流，但是边太多（完全二分图），会被卡掉。
正解：KM算法
一个不错的博客，但是有些东西还是不是很明白。
http://blog.sina.com.cn/s/blog_691ce2b701016reh.html
关于他写的最后一句，每次要更新stack，实测本题不需要，可能别的地方会用到，以后再讨论。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 int dis[303][303]; 8 int lx[333],ly[333]; 9 int mind[333]; 10 int visx[333]; 11 int visy[333]; 12 int match[333]; 13 int N; 14 bool dfs(int u) 15 { 16 visx[u] = 1; 17 for (int i = 1; i<= N; i++) 18 { 19 if (visy[i]) continue; 20 int t = lx[u] + ly[i] - dis[u][i]; 21 if (t == 0) 22 { 23 visy[i] = 1; 24 if (match[i]==-1 || dfs(match[i])) 25 { 26 match[i] = u; 27 return true; 28 } 29 } 30 else if (mind[i] > t) 31 { 32 mind[i] = t; 33 } 34 } 35 return false; 36 } 37 int KM() 38 { 39 memset(ly,0,sizeof(lx)); 40 memset(match,-1,sizeof(match)); 41 //枚举一方面的点 42 for (int i = 1 ;i<=N; i++) 43 { //储存最小的mind 44 memset(mind,inf,sizeof(mind)); 45 memset(visx,0,sizeof(visx)); 46 memset(visy,0,sizeof(visy)); 47 while (!dfs(i)) //这里需要多次dfs同一个点，因为更改lx和ly会使得需要再次dfs 48 { 49 int d = inf; 50 for (int j = 1 ; j<=N; j++) 51 { 52 if (!visy[j]) d = min(d,mind[j]); 53 } 54 for (int j = 1; j<=N; j++) 55 { 56 if (visx[j]) lx[j]-=d; 57 if (visy[j]) ly[j]+=d; 58 } 59 memset(visx,0,sizeof(visx)); 60 memset(visy,0,sizeof(visy)); 61 } 62 } 63 int ans = 0; 64 for (int i= 1;i<= N;i++) 65 ans += dis[match[i]][i]; 66 return ans; 67 } 68 int main() 69 { 70 while (scanf ("%d",&N)!=EOF) 71 { 72 for (int i = 1; i<=N;i++) 73 lx[i] = -inf; 74 for (int i = 1 ; i<= N; i++) 75 { 76 for (int j = 1; j <= N; j++) 77 { 78 scanf("%d",&dis[i][j]); 79 lx[i] = max(lx[i],dis[i][j]); 80 } 81 } 82 printf ("%d ",KM()); 83 } 84 }