杭电2255 奔小康赚大钱（二分图最有匹配KM算法）

题目链接：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 }