poj 2195Going Home

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstdlib>
  7 #define maxn 500
  8 using namespace std;
  9 int n,mm;
 10 char g[maxn][maxn];
 11 const int inf=1<<30;
 12 
 13 struct node
 14 {
 15     int x,y;
 16 }m[maxn];
 17 
 18 struct node1
 19 {
 20     int x,y;
 21 }h[maxn];
 22 
 23 int cap[maxn][maxn];
 24 int cost[maxn][maxn];
 25 int flow[maxn][maxn];
 26 int p[maxn];
 27 int s,t;
 28 int main()
 29 {
 30     while(scanf("%d%d",&n,&mm)&&n&&mm)
 31     {
 32         memset(cap,0,sizeof(cap));
 33         memset(cost,0,sizeof(cost));
 34         int t1=0,t2=0;
 35         for(int i=0; i<n; i++)
 36         {
 37             scanf("%s",g[i]);
 38             for(int j=0; j<mm; j++)
 39             {
 40                 if(g[i][j]=='m')
 41                 {
 42                     m[++t1].x=i;
 43                     m[t1].y=j;
 44                 }
 45                 else if(g[i][j]=='H')
 46                 {
 47                     h[++t2].x=i;
 48                     h[t2].y=j;
 49                 }
 50             }
 51         }
 52         for(int i=1; i<=t1; i++)
 53         {
 54             cap[0][i]=1;
 55             cost[0][i]=0;
 56         }
 57         for(int i=1; i<=t1; i++)
 58         {
 59             for(int j=1; j<=t2; j++)
 60             {
 61                 cap[i][t1+j]=1;
 62                 cost[i][t1+j]=abs(m[i].x-h[j].x)+abs(m[i].y-h[j].y);
 63                 cost[t1+j][i]=-cost[i][t1+j];
 64             }
 65         }
 66         for(int j=1; j<=t2; j++)
 67         {
 68             cap[t1+j][t1+t2+1]=1;
 69             cost[t1+j][t1+t2+1]=0;
 70         }
 71         s=0,t=t1+t2+1;
 72         queue<int>q;
 73         int d[maxn];
 74         memset(flow,0,sizeof(flow));
 75         int c=0,f=0;
 76         for(;;)
 77         {
 78             bool inq[maxn];
 79             for(int i=0; i<=t1+t2+1; i++) d[i]=(i==0?0:inf);
 80             memset(inq,0,sizeof(inq));
 81             q.push(s);
 82             while(!q.empty())
 83             {
 84                 int u=q.front();q.pop();
 85                 inq[u]=false;
 86                 for(int v=0; v<=t1+t2+1; v++) if(cap[u][v]>flow[u][v] && d[v]>d[u]+cost[u][v])
 87                 {
 88                     d[v]=d[u]+cost[u][v];
 89                     p[v]=u;
 90                     if(!inq[v])
 91                     {
 92                         inq[v]=true;
 93                         q.push(v);
 94                     }
 95                 }
 96             }
 97             if(d[t]==inf) break;
 98             int a=inf;
 99             for(int u=t; u!=s; u=p[u])
100             {
101                 if(cap[p[u]][u]-flow[p[u]][u]<a)
102                 {
103                     a=cap[p[u]][u]-flow[p[u]][u];
104                 }
105             }
106             for(int u=t; u!=s; u=p[u])
107             {
108                 flow[p[u]][u]+=a;
109                 flow[u][p[u]]-=a;
110             }
111             c+=d[t]*a;
112             f+=a;
113         }
114         printf("%d
",c);
115     }
116     return 0;
117 }
View Code