http://poj.org/problem?id=2195
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,tt;
struct pointe
{
int x,y;
} l[],r[];
struct node
{
int x,y,c,w;
int next;
} eg[];
char map[][];
int head[],v[],dis[],pre[];
void init()
{
memset(head,-,sizeof(head));
tt=;
s=;
t=n*m+;
}
void add(int xx,int yy,int cc,int ww)
{
eg[tt].x=xx;
eg[tt].y=yy;
eg[tt].c=cc;
eg[tt].w=ww;
eg[tt].next=head[xx];
head[xx]=tt++;
eg[tt].x=yy;
eg[tt].y=xx;
eg[tt].c=;
eg[tt].w=-ww;
eg[tt].next=head[yy];
head[yy]=tt++;
}
int spfa(int s,int t)
{
for(int i=s; i<=t; i++)
{
v[i]=;
pre[i]=-;
dis[i]=inf;
}
queue<int>q;
dis[s]=;
q.push(s);
while(!q.empty())
{
int ff=q.front();
q.pop();
v[ff]=;
//今天算是刚了解邻接边表第一次更新的是与源点相邻的第一层
//例如head[10]->1,3,5,7....;
for(int i=head[ff]; i!=-; i=eg[i].next)
{
int w1=eg[i].y;
if(eg[i].c&&dis[w1]>dis[ff]+eg[i].w)
{
dis[w1]=dis[ff]+eg[i].w;//注意这里dis[ff]
pre[w1]=i;//算是了解么意思了
if(!v[w1])
{
v[w1]=;
q.push(w1);
}
}
}
}
if(dis[t]==inf)
{
return ;
}
return ;
}
void KM(int s,int t)
{
int ans=,minx;
while(spfa(s,t)==)
{
minx=inf;
for(int i=pre[t]; i!=-; i=pre[eg[i].x])
minx=min(minx,eg[i].c);
for(int i=pre[t]; i!=-; i=pre[eg[i].x])
{
eg[i].c-=minx;
eg[i+].c+=minx;
}
ans+=minx*dis[t];
}
cout<<ans<<endl;
return ;
}
int main()
{
int t1,t2,temp;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
t1=t2=;
init();
for(int i=; i<=n; i++)
scanf("%*c%s",map[i]+);
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
temp=(i-)*m+j;
if(map[i][j]=='m')
{
add(s,temp,,);
l[t1].x=i;
l[t1++].y=j;
}
else if(map[i][j]=='H')
{
add(temp,t,,);
r[t2].x=i;
r[t2++].y=j;
}
}
}
for(int i=; i<t1; i++)
{
int l1=(l[i].x-)*m+l[i].y;
for(int j=; j<t2; j++)
{
int l2=(r[j].x-)*m+r[j].y;
int l3=abs(l[i].x-r[j].x)+abs(l[i].y-r[j].y);
add(l1,l2,,l3);
}
}
KM(s,t);
}
return ;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <math.h>
#define inf 0x3f3f3f3f
using namespace std;
struct node1//记录h或者m的坐标
{
int x,y;
} a[],b[];
struct node
{
int x,y,c,w;
int next;
} eg[];
int n,m,tt,head[],v[],dis[],pre[],s,t;
char map[][];
void init()
{
tt=;
memset(head,-,sizeof(head));
s=;
t=n*m+;
}
void add(int xx,int yy,int cc,int ww)
{
eg[tt].x=xx;
eg[tt].y=yy;
eg[tt].c=cc;
eg[tt].w=ww;
eg[tt].next=head[xx];
head[xx]=tt++;
eg[tt].x=yy;
eg[tt].y=xx;
eg[tt].c=;
eg[tt].w=-ww;
eg[tt].next=head[yy];
head[yy]=tt++;
}
int spfa(int s,int t)
{
queue<int>q;
for(int i=; i<=t; i++)
{
v[i]=;
dis[i]=inf;
pre[i]=-;
}
v[s]=;
dis[s]=;
q.push(s);
while(!q.empty())
{
int ff=q.front();
q.pop();
v[ff]=;
for(int i=head[ff]; i!=-; i=eg[i].next)
{
int w1=eg[i].y;
if(eg[i].c&&dis[w1]>dis[ff]+eg[i].w)
{
dis[w1]=dis[ff]+eg[i].w;
pre[w1]=i;//用边表建图存储其信息
if(!v[w1])
{
v[w1]=;
q.push(w1);
}
}
}
}
if(dis[t]==inf)
{
return ;
}
return ;
}
void KM(int s,int t)
{
int min1,ans=;
while(spfa(s,t)==)
{
min1=inf;
for(int i=pre[t]; i!=-; i=pre[eg[i].x])
{
if(min1>=eg[i].c)
{
min1=eg[i].c;
}
}
for(int i=pre[t]; i!=-; i=pre[eg[i].x])
{
eg[i].c-=min1;
eg[i+].c+=min1;
}
ans+=min1*dis[t];
}
printf("%d\n",ans);
return ;
}
int main()
{
int t1,t2;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==) break;
init();
t1=;
t2=;
for(int i=; i<=n; i++)
{
scanf("%s",map[i]+);//因为要创建超级源点，所以从一比较好计算
for(int j=; j<=m; j++)
{
int l=(i-)*m+j;//以点建图
if(map[i][j]=='m')
{
add(s,l,,);
a[t1].x=i;
a[t1++].y=j;
}
else if(map[i][j]=='H')
{
add(l,t,,);
b[t2].x=i;
b[t2++].y=j;
}
}
}
for(int i=; i<t1; i++)
{
int l1=(a[i].x-)*m+a[i].y;//以点建图
for(int j=; j<t2; j++)
{
int l2=abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y);
int l3=(b[j].x-)*m+b[j].y;//以点建图
add(l1,l3,,l2);
}
}
KM(s,t);
}
return ;
}