#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<cmath>
#define Max 3276700
using namespace std;
struct Node_type
{
	int x,y;
};
int n,N,M,c[300][300],f[300][300],cost[300][300],v[300][300],S,T,d[300],adj[300],pre[300],ans;
vector<Node_type> M_map;
vector<Node_type> H_map;
queue<int> Q;
void Init()
{
	M_map.clear();
	H_map.clear();
	char ch;
	Node_type temp;
	ans=0;
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
		{
			cin>>ch;
			temp.x=i;temp.y=j;
			if(ch=='m')
				M_map.push_back(temp);
			if(ch=='H')
				H_map.push_back(temp);
		}
	memset(f,0,sizeof(f));
	for(int i=0;i<300;i++)
		for(int j=0;j<300;j++)
			cost[i][j]=Max;

	for(unsigned int i=0;i<M_map.size();i++)
		for(unsigned int j=0;j<H_map.size();j++)
			cost[i][M_map.size()+j]=abs(M_map[i].x-H_map[j].x)+abs(M_map[i].y-H_map[j].y);
	n=2*M_map.size();
	S=n;T=n+1;
	for(int i=0;i<M_map.size();i++)
		cost[S][i]=0;
	for(int i=M_map.size();i<n;i++)
		cost[i][T]=0;
	n+=2;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			c[i][j]=1;
}
inline int min(int x,int y)
{
	return ((x<y)?x:y);
}

int spfa()
{
	bool checked[300];
	while(!Q.empty())Q.pop();
	memset(checked,0,sizeof(checked));
	Q.push(S);checked[S]=true;
	for(int i=0;i<n;i++)d[i]=Max;
	d[S]=0;
	while(!Q.empty())
	{
		int t=Q.front();
		Q.pop();
		checked[t]=false;
		for(int i=0;i<n;i++)
		{
			if(f[i][t]>0)
			{
				if(d[i]>d[t]-cost[i][t])
				{
					d[i]=d[t]-cost[i][t];
					if(!checked[i])
					{
						checked[i]=true;
						Q.push(i);
					}
					pre[i]=-t;
				}
			}else
				if(f[t][i]<c[t][i])
				{
					if(d[i]>d[t]+cost[t][i])
					{
						d[i]=d[t]+cost[t][i];
						if(!checked[i])
						{
							checked[i]=true;
							Q.push(i);
						}
						pre[i]=t;
					}
				}
		}
	}
	return d[T];
}

inline void adjust()
{
	int temp=T;
	while(temp!=S)
	{
		if(pre[temp]>0)
		{
			f[pre[temp]][temp]++;
			temp=pre[temp];
		}else
		{
			f[temp][-pre[temp]]--;
			temp=-pre[temp];
		}
	}
}

void work()
{
	while(true)
	{
		int d=spfa();
		if(d==Max)break;
		adjust();
		ans+=d;
	}
	cout<<ans<<endl;
}

int main()
{
	cin>>N>>M;
	while(!(M==0 && N==0))
	{
		Init();
		work();
		cin>>N>>M;
	}
	return 0;
}

• Re:为什么我用km可以ac用费用流却wa呢。。 (140) Iambitious 2007-03-20 09:56:11
  • Re:为什么我用km可以ac用费用流却wa呢。。 (35) Iambitious 2007-03-22 12:15:14