题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2255
[KM算法的几种转化]
KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。
（详细关于KM算法讲解：http://blog.163.com/huangbingliang@yeah/blog/static/94161399201011291044527/
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int n; 4 int map[310][310],a[310],b[310]; 5 int sx[310],sy[310],f[310]; 6 int find(int x) 7 { 8 int i; 9 f[x]=1; 10 for(i=1;i<=n;i++) 11 { 12 if(b[i]==0&&map[x][i]==sx[x]+sy[i]) 13 { 14 b[i]=1; 15 if(a[i]==-1||find(a[i])) 16 { 17 a[i]=x; 18 return 1; 19 } 20 } 21 } 22 return 0; 23 } 24 25 void met() 26 { 27 int i,j,k,min; 28 for(i=1;i<=n;i++) 29 { 30 while(1) 31 { 32 memset(f,0,sizeof(f)); 33 memset(b,0,sizeof(b)); 34 if(find(i)) 35 break; 36 min=2147483647; 37 for(j=1;j<=n;j++) 38 { 39 if(f[j]) 40 { 41 for(k=1;k<=n;k++) 42 if(b[k]==0) 43 min=min>(sx[j]+sy[k]-map[j][k])?(sx[j]+sy[k]-map[j][k]):min; 44 } 45 } 46 for(j=1;j<=n;j++) 47 if(f[j]) 48 sx[j]-=min; 49 for(k=1;k<=n;k++) 50 if(b[k]) 51 sy[k]+=min; 52 } 53 } 54 } 55 int main() 56 { 57 int i,j,num; 58 while(scanf("%d\n",&n)!=-1) 59 { 60 memset(map,0,sizeof(map)); 61 memset(sx,0,sizeof(sx)); 62 memset(sy,0,sizeof(sy)); 63 memset(a,-1,sizeof(a)); 64 for(i=1;i<=n;i++) 65 { 66 for(j=1;j<=n;j++) 67 { 68 scanf("%d",&map[i][j]); 69 if(sx[i]<map[i][j]) 70 sx[i]=map[i][j]; 71 } 72 } 73 met(); 74 num=0; 75 for(i=1;i<=n;i++) 76 if(a[i]) 77 num+=map[a[i]][i]; 78 printf("%d\n",num); 79 } 80 return 0; 81 }