HDU 1533 & KM模板

题意

　　求二分图最小完备匹配。

SOL

　　建个图那么方便的事情是吧。。。然后边权都是正的（好像根边权也没什么关系），既然要求最小那么把边权取个相反数跑个KM就好了。。

CODE：

/*==========================================================================

# Last modified: 2016-02-16 19:55

# Filename: hdu1533.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

CODE：

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define lowbit(x) (x)&(-x)

#define INF 1070000000

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define maxn 200

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

/*==================split line==================*/

int n,sumx,sumy;

int w[maxn][maxn],link[maxn],lx[maxn],ly[maxn],slack[maxn],x[maxn],y[maxn];

bool S[maxn],T[maxn];

int calc(int i,int j){

	int y1=x[i]%1000,x1=x[i]/1000,y2=y[j]%1000,x2=y[j]/1000;

	return -(abs(y1-y2)+abs(x1-x2));

}

void build_graph(){

	FORP(i,1,n)

		FORP(j,1,n)

			w[i][j]=calc(i,j);

}

bool match(int i){

	S[i]=true;

	FORP(j,1,n){

		if (T[j]) continue;

		int tmp=lx[i]+ly[j]-w[i][j];

		if (tmp==0){

			T[j]=true;

			if (!link[j] || match(link[j])){

				link[j]=i;

				return true;

			}

		}

		else slack[j]=min(slack[j],tmp);

	}

	return false;

}

void updata(){

	int a=INF;

	FORP(i,1,n) if (!T[i]) a=min(a,slack[i]);

	FORP(i,1,n) {

		if (S[i]) lx[i]-=a;

		if (T[i]) ly[i]+=a;

			else slack[i]-=a;

	}

}

int KM(){

	memset(link,0,sizeof(link));

	memset(ly,0,sizeof(ly));

	FORP(i,1,n)

		FORP(j,1,n) lx[i]=max(lx[i],w[i][j]);

	FORP(i,1,n){

		memset(slack,0x7f,sizeof(slack));

		while (1){

			memset(S,false,sizeof(S));

			memset(T,false,sizeof(T));

			if (match(i)) break;

			else updata();

		}

	}

	int ans=0;

	FORP(i,1,n) if (link[i])

	ans+=w[link[i]][i];

	return -ans;

}

int main(){

	//freopen("a.in","r",stdin);

	int r,c;

	while (1){

		sumx=0; sumy=0;

		scanf("%d%d",&r,&c);

		if (r==0 && c==0) return 0;

		FORP(i,1,r){

			char ch[1000];

			scanf("%s",ch);

			FORP(j,0,c-1)

				if (ch[j]=='m') x[++sumx]=i*1000+j+1;

				else if (ch[j]=='H') y[++sumy]=i*1000+j+1;

		}

		n=sumx;

		build_graph();

		printf("%d\n",KM());

	}

}