poj 2195 km算法求最佳匹配

 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 101
#define MAX_INT 2000000

#define min(a, b) (a) < (b) ? (a) : (b)
#define max(a, b) (a) > (b) ? (a) : (b)

using namespace std;

int 	weight[N][N];	/* X集合点到Y集合点的权重 */
int		lx[N], ly[N];	/* 标号 */
char	visitx[N], visity[N];	/* 用于深度搜索，同时可以标记S和T集合的点 */
int		mat[N];		/* mat[y] = x，表示集合Y的y点的匹配为x */
int		slack[N];	/* slack[x]保存相对与顶点x的最小al,初始时为无穷大,  dfs寻找增广路径的时候不断更新，并且会越来越小 */
int		nx, ny;

struct 	position {
	int x;
	int y;
};

/* 从顶点x开始深度优先寻找增广路径, 寻找的过程中同时更新slack数组
 * 和mat数组，若找到返回1
 * 若找不到返回0，此时visitx[x] = 1的点属于S集合
 * visity[y] = 1的点属于T集合 
 */
int find(int x) 
{
	int		y, t;

	visitx[x] = 1;
	debug("访问顶点X.%d\n", x);
	for (y = 1; y <= ny; y++) {
		if (!visity[y] && weight[x][y] != 0) {
			t = lx[x] + ly[y] - weight[x][y];
			if (t != 0) {
				slack[x] = min(slack[x], t);
			}
			else {
				visity[y] = 1;
				debug("访问顶点Y.%d\n", y);
				if ((mat[y] == -1 || find(mat[y]))) {
					mat[y] = x;
					return 1;
				}
				debug("否定顶点Y.%d\n", y);
			}
		}
	}
	return 0;
}

int main()
{
	int		x, y, s, min_al, cost, m, n;
	char	ch;
	struct 	position man[N], home[N];

	while (cin>>m>>n, m) {
		//初始化l[v]
		memset(weight, 0, sizeof(weight));
		memset(ly, 0, sizeof(ly));
		memset(mat, -1, sizeof(mat));
		for (x = 1; x <= N; x++) {
			lx[x] = -2000000; 
			slack[x] = MAX_INT;
		}
		//输入数据
		nx = ny = 0;
		for (x = 1; x <= m; x++) {
			for (y = 1; y <= n; y++) {
				cin >> ch;
				if (ch == 'm') {
					man[++nx].x = x;
					man[nx].y = y;
				}
				else if (ch == 'H') {
					home[++ny].x = x;
					home[ny].y = y;
				}
			}
		}
		//建图
		for (x = 1; x <= nx; x++) {
			for (y = 1; y <= ny; y++) {
				weight[x][y] = abs(man[x].x-home[y].x) + abs(man[x].y-home[y].y);
				weight[x][y] *= -1;		/* 题目要求最小权匹配，故把权值乘以-1，转变成求最大权匹配 */
				lx[x] = max(lx[x], weight[x][y]);	/* lx[x]初始化为最大权值 */
			}
		}

		//给每个顶点寻找增广路径，若找不到就重新标号
		for (s = 1; s <= nx;) {
			for (;;) {	
				memset(visitx, 0, sizeof(visitx));
				memset(visity, 0, sizeof(visity));
				if (find(s)) {
					s++;
					debug("增广路径找到...\n");
					break;
				}
				debug("从顶点%d找不到增广路径, 更新顶点标号...\n", s);
				//在S集合中找最小的lx[x]+ly[y]-weight[x][y], 借助slack数组
				min_al = MAX_INT;
				for (x = 1; x <= nx; x++) {
					if (visitx[x] && slack[x] < min_al) {
						min_al = slack[x];
					}
				}
				//更新S集合和T集合顶点标号
				for (x = 1; x <= nx; x++) {
					if (visitx[x]) lx[x] -= min_al;
				}
				for (y = 1; y <= ny; y++) {
					if (visity[y]) ly[y] += min_al;
				}
			}
		}
		//打印匹配结果
		for (y = 1; y <= ny; y++) {
			if (mat[y] != -1) {
				debug("X.%d-->Y.%d %d\n", mat[y], y, weight[mat[y]][y]);
			}
		}
		//计算最大权
		cost = 0;
		for (x = 1; x <= nx; x++) {
			cost += lx[x];
		}
		for (y = 1; y <= ny; y++) {
			cost += ly[y];
		}
		printf("%d\n", -cost);
	}
	return 0;
}