此题为基本的KM匹配题目，在Hdu做的时候是在网络流专题里面，所以用最小费用最大流做了一下。这也是我第一次写最小费用最大流算法。
         其中第一次为了采用标号法，使用dijkstra最短路来拓展增广路径，其中为了避免负权情况采用了一下策略：
将 G中有流边（f(e)＞0）的权w(e)修正为0。为此， 每次在增流网络上求得最短路径后，以下式计算G中新的边权w " (u,v)：

                                                w " (u,v)=L(u)-L(v)+w(u,v) (*)

　　式中 L(u),L(v) -- 计算G′的x至y最短路径时u和v的标号值。第一次求最短径时如果(u,v)是增流路径上的边， 则据最短 路径算法一定有 L(v)=L(u)+w ' (u,v)=L(u)+w(u,v)， 代入(*)式必有

                                                              w″(u,v)=0。

如果(u,v)不是增流路径上的边，则一定有：
　　　                                                 L(v)≤L(u)+w(u,v)，
代入(*)式则有 w(u,v)≥0。

　　可见第一次修正w(e)后，对任一边，皆有w(e)≥0， 且有流 的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若 f(u,v)＞0，增流网络需建立(v,u)边，边权数w ' (v,u)=-w(u,v) =0，即不会再出现负权边。
    此外，每次迭代计算用(*)式修正一切w(e)， 不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)-L(y)。因此，x至y的最短路径不会因对w(e)的修正而发生变化。

可是很悲剧的是，虽然我过了很多大数据，而且在POJ上面顺利的AC了。可惜当我提交的hduOJ上面的时候却WA了。。。。

检查了好久也没发现错误，很崩溃。。。。代码如下：

  1#include "stdio.h"
  2#include "string.h"
  3#include "math.h"
  4#define N 500
  5#define INF 100000000
  6struct Nod
  7{
  8    int r;
  9    int c;
 10};
 11struct Edge
 12{
 13    int w;
 14    int c;
 15};
 16Nod hou[N];
 17Nod man[N];
 18Edge c[N][N];
 19char grid[N][N];
 20int Row,Col,n,sc,sk;
 21int d[N],s[N];
 22int augc;
 23int flow;
 24bool flag[N];
 25
 26void Map()
 27{
 28    int i,j;
 29    for(i=0;i<n;i++)
 30    {
 31        for(j=0;j<n;j++)
 32        {
 33            if(c[i][j].c>0)
 34            {
 35                if(c[i][j].w==INF) 
 36                    c[i][j].w=0;
 37                else
 38                    c[i][j].w=d[i]+c[i][j].w-d[j];
 39            }
 40        }
 41    }
 42}
 43
 44bool Dij()
 45{
 46    int i,j,minDis,u;
 47    for(i=0;i<n;i++)
 48    {
 49        if(c[sc][i].c>0)
 50                d[i]=c[sc][i].w;
 51        else d[i]=INF;
 52        s[i]=0;
 53    }
 54    d[sc]=0;
 55    s[sc]=1;
 56    for(i=0;i<n;i++)
 57    {
 58        minDis=INF;
 59        for(j=0;j<n;j++)
 60        {
 61            if(s[j]==0 && d[j]<minDis)
 62            {
 63                u=j;
 64                minDis=d[j];
 65            }
 66        }
 67        if(minDis==INF)
 68        {
 69            if(d[sk]<INF) return true;
 70            else return false;
 71        }
 72        s[u]=1;
 73        for(j=0;j<n;j++)
 74        {
 75            if((s[j]==0) && (c[u][j].w<INF) && (c[u][j].c>0) && (d[u]+c[u][j].w<d[j]))
 76            {
 77                d[j]=d[u]+c[u][j].w;
 78            }
 79        }
 80    }
 81    if(d[sk]<INF) return true;
 82    else return false;
 83}
 84
 85bool aug(int v)
 86{
 87    int i,augco;
 88    augco=augc;
 89    flag[v]=true;
 90    if(v==sk)
 91    {
 92        flow+=augc;
 93        return true;
 94    }
 95    for(i=1;i<n;i++)
 96    {
 97        if((c[v][i].c>0)&&(!flag[i]))
 98        {
 99            if(d[i]==d[v]+c[v][i].w)
100            {
101                if(c[v][i].c<augc)
102                    augc=c[v][i].c;
103                if(aug(i)) 
104                {
105                    c[v][i].c-=augc;
106                    c[i][v].c+=augc;
107                    return true;
108                }
109                augc=augco;
110            }
111        }
112    }
113    return false;
114}
115void Print()
116{
117    int i,j;
118    int tem;
119    for(i=0;i<n;i++)
120    {
121        for(j=0;j<n;j++)
122        {
123            tem=c[i][j].w;
124            if(tem==INF) tem=-1;
125            printf("%d(%d) ",c[i][j].c,tem);
126        }
127        printf("\n");
128    }
129}
130void MSMF()
131{
132    int ans=0;
133    flow=0;
134    int tem=0;
135    while(1)
136    {
137        if(!Dij()) break;
138        ans+=tem+d[sk];
139        tem+=d[sk];
140        augc=INF;    
141        memset(flag,false,sizeof(flag));
142        if(!aug(sc))break;
143        Map();
144    //    Print();
145    }
146    printf("%d\n",ans);
147}
148int main()
149{
150    int i,j,mn,hn,t;
151    while(scanf("%d %d",&Row,&Col)!=EOF)
152    {
153        if(!Row && !Col) break;
154        for(i=0;i<Row;i++)
155        {
156            scanf("%s",grid[i]);
157        }
158        mn=1;
159        hn=1;
160        sc=0;
161        for(i=0;i<Row;i++)
162        {
163            for(j=0;j<Col;j++)
164            {
165                if(grid[i][j]=='H')
166                {
167                    hou[hn].r=i+1;
168                    hou[hn++].c=j+1;
169                }
170                else if(grid[i][j]=='m')
171                {
172                    man[mn].r=i+1;
173                    man[mn++].c=j+1;
174                }
175            }
176        }
177        if(mn!=hn) 
178        {
179            printf("0\n");
180            continue;
181        }
182        t=mn-1;
183        n=2*t+2;    
184        for(i=0;i<n;i++)
185        {
186            for(j=0;j<n;j++)
187            {
188                c[i][j].w=INF;
189                c[i][j].c=0;
190            }
191        }    
192        sk=n-1;
193        for(i=1;i<=t;i++)
194        {
195            c[sc][i].w=0;
196            c[sc][i].c=1;
197            c[i+t][sk].w=0;
198            c[i+t][sk].c=1;
199        }
200        for(i=1;i<=t;i++)
201        {
202            for(j=1;j<=t;j++)
203            {
204                c[i][j+t].w=abs(man[i].r-hou[j].r)+abs(man[i].c-hou[j].c);
205                c[i][j+t].c=1;
206            }
207        }
208    //    Print();
209        MSMF();
210    }
211    return 0;
212}
213


 WA了之后肯定是很无奈，也很郁闷，所以决定采用SPFA来扩展找增广路，于是我拿出自己的SPFA模板，很快就改好了，结果很顺利的在hduoj上面AC了。。。。代码如下：



那么为什么呢？经过仔细的重新查看算法步骤，发现33-39行的更新不是很完备，对于c[i][j]==0时应该也进行同样的权值更变，以保证任何一条路径的值增加为lx[]-ly[]；更正后果然，顺利ac了。