#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 205;
const int inf = 9999999;
struct edge
{
       int from,to,next,val,cost;
}e[maxn*maxn];
struct point
{
       int x,y;
       point(int a=0,int b=0)
       {  x=a; y=b; }
}hp[maxn],mp[maxn];
int index,head[maxn],pre[maxn],vis[maxn],dist[maxn],pos[maxn];
void addedge(int from,int to,int f,int c)
{
     e[index].from=from,e[index].to=to,e[index].val=f,e[index].cost=c,e[index].next=head[from];
     head[from] = index++;
     e[index].from=to,e[index].to=from,e[index].val=0,e[index].cost=-c,e[index].next=head[to];
     head[to] = index++;
}
bool spfa(int s,int t,int n)
{
     memset(pre,-1,sizeof(pre));
     memset(vis,0,sizeof(vis));
     for(int i = 1;i <= n;i++)  dist[i] = inf;
     queue<int>que;
     int p;
     que.push(s);  pre[s]=s; dist[s] = 0; vis[s] = 1;
     while(!que.empty())
     {
          p = que.front();  que.pop();   vis[p] = 0;    
          for(int q = head[p]; q != -1; q = e[q].next)
          {
                
               if(e[q].val > 0 && dist[e[q].to] > e[q].cost + dist[e[q].from])
               {
                    dist[e[q].to] =  e[q].cost + dist[e[q].from];
                    pre[e[q].to] = e[q].from;   
                    pos[e[q].to] = q;
                    if(!vis[e[q].to])
                    {
                         vis[e[q].to] = 1;
                         que.push(e[q].to);
                    }
               }
          }
     }
     return (pre[t] != -1 && dist[t] < inf);
}
int minCostFlow(int s,int t,int n)
{
     int cost = 0;
     while(spfa(s,t,n))
     {
          int f1 = inf;
          for(int i = t; i != s; i = pre[i])
                f1 = min(f1,e[pos[i]].val);
          cost+=f1*dist[t];
          for(int i = t; i != s; i = pre[i])
          {
                e[pos[i]].val -= f1;
                e[pos[i]^1].val += f1;
          }
     }
     return cost;
}
int main()
{
    int n,m,xM[maxn],yM[maxn];
    char ch[maxn];
    while(scanf("%d%d",&m,&n)!=EOF && (m || n))
    {
          int n_hp=0, n_mp=0;
          for(int i = 1;i <= m;i++)
          {
               scanf("%s",ch);
               for(int j=0;j<n;j++)
               {
                   if(ch[j] == 'H')
                      hp[++n_hp] = point(i,j+1);
                   else if(ch[j] == 'm')
                      mp[++n_mp] = point(i,j+1);
               }        
          }
          index = 0;
          memset(head,-1,sizeof(head));
          for(int i=1;i<=n_hp;i++)
          {
                for(int j=1;j<=n_mp;j++)
                {  
                    int l=abs(hp[i].x-mp[j].x)+abs(hp[i].y-mp[j].y);   
                    addedge(i,j+n_hp,1,l); 
                }
                    
          }
          for(int i=1;i<=n_hp;i++)
               addedge(1+n_hp+n_mp,i,1,0); 
          for(int i=1;i<=n_mp;i++)
               addedge(i+n_hp,2+n_hp+n_mp,1,0);
   
          printf("%d\n",minCostFlow(1+n_hp+n_mp,2+n_hp+n_mp,2+n_hp+n_mp));
    }
    return 0;
}

• 膜拜下，代码里有SPFA，最小费用流。。 (2) lzs1991 2010-09-21 01:51:07