poj2195——Going Home

最小权值匹配，跟最大权值匹配差不多，但有些地方需改变：

1：

t=gg[u][v]-lx[u]-ly[v];

2：

for(i=0;i<topx;i++)
	{
		min=1000;
		for(j=0;j<topy;j++)
			if(gg[i][j]<min)min=gg[i][j];
		lx[i]=min;
	}

3：

for(j=0;j<topx;j++)  if(vx[j])   lx[j]+=d;
			for(j=0;j<topy;j++)  if(vy[j])   ly[j]-=d;

其他地方基本是最大匹配的模板。当然，这题还可以用MAX-其权值，反过来求最大匹配！

#include<stdio.h>
#include<string.h>
char g[102][102];
#define max 5002
struct node
{
	int x,y;
}cx[max],cy[max];
int gg[max][max];
int n,m,topx,topy;
int fbs(int a){ if(a>=0) return a;else return -a;}
int lx[max],ly[max],my[max],slack[max];
bool vx[max],vy[max];
bool dfs(int u)
{
	int v,t;
	vx[u]=1;
	for(v=0;v<topy;v++)
	{
		if(!vy[v])
		{
			t=gg[u][v]-lx[u]-ly[v];
			if(t==0)
			{
				vy[v]=1;
				if(my[v]==-1||dfs(my[v]))
				{
					my[v]=u;return true;
				}
			}
			else slack[v]=slack[v]<t?slack[v]:t;
		}
	}
	return false;
}
void KM()
{
	int i,j,min,d;
	for(i=0;i<topx;i++)
	{
		min=1000;
		for(j=0;j<topy;j++)
			if(gg[i][j]<min)min=gg[i][j];
		lx[i]=min;
	}
	memset(ly,0,sizeof(ly));
	memset(my,-1,sizeof(my));
	for(i=0;i<topx;i++)
	{
		memset(slack,127,sizeof(slack));
		while(1)
		{
			memset(vx,0,sizeof(vx));
		    memset(vy,0,sizeof(vy));
			if(dfs(i))
				break;
			d=max;
			for(j=0;j<topy;j++)  if(!vy[j])  d=d<slack[j]?d:slack[j];
			for(j=0;j<topx;j++)  if(vx[j])   lx[j]+=d;
			for(j=0;j<topy;j++)  if(vy[j])   ly[j]-=d;
		}
	}
	int ans=0;
	for(i=0;i<topy;i++)
	{
		if(my[i]!=-1)
			ans+=gg[my[i]][i];
	}
	printf("%d\n",ans);
}
int main()
{
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		topx=0;topy=0;
		if(n==0&&m==0)
			break;
		for(i=1;i<=n;i++)
			scanf("%s",&g[i]);
		for(i=1;i<=n;i++)
			for(j=0;j<m;j++)
			{
				if(g[i][j]=='H'){
					cy[topy].x=i;cy[topy].y=j+1;
					topy++;
				}
				else if(g[i][j]=='m'){
					cx[topx].x=i;cx[topx].y=j+1;
					topx++;
				}
			}
			for(i=0;i<topx;i++)
			{
				for(j=0;j<topy;j++){
					gg[i][j]=fbs(cx[i].x-cy[j].x)+fbs(cx[i].y-cy[j].y);
				}
			}
				KM();
	}
}