2195(1) km.cpp

各种算法

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
int HCount, MCount;
struct Pos
{
	int x;
	int y;
};
struct Pos* Man[SIZE];
struct Pos* House[SIZE];

int Weight[SIZE][SIZE];
int XSize, YSize;
int dog[SIZE], god[SIZE];
bool chart[SIZE][SIZE];

template<class T>
inline T Abs(T a)
{
if (a < 0)
   return (-a);
return a;
}

bool findBestMatch()
{
	int i, j, k;
	int X[SIZE], Y[SIZE];
	for (i = 0; i < XSize; ++i){
	   for(j = 0; j < YSize; ++j){
			if (j == 0)  X[i] = Weight[i][j];
			else
			X[i] = (X[i] > Weight[i][j] ? X[i]:Weight[i][j]);
	   }
	   dog[i] = -1;
	}
	for (i = 0; i < YSize; ++i){
	   Y[i] = 0;
	   god[i] = -1;
	}
	k = 0;
	while (k < XSize){
		while (dog[k] == -1){
			for (i = 0; i < XSize; ++i){//初始化等式子图,其实只需初始x~y(x属于S，y属于　Y - t)
				for (j = 0; j < YSize; ++j){
					if (X[i] + Y[j] == Weight[i][j])
						chart[i][j] = true;
					else
						chart[i][j] = false;
				}
			}
			int queue[SIZE], Begin = 0, End = 0;//建立一个队列，end前为己匹配，后为未匹配
			int trace[SIZE];
			for (i = 0; i < YSize; ++i){//Pick k to S:(trace),初始化T为空
				queue[i] = i;
l1:				if (chart[k][queue[i]]){
					trace[queue[i]] = k;
					j = queue[i]; queue[i] = queue[End]; queue[End++] = j;
				}
				else trace[i] = -1;
			}					//queue[End]前为有匹配的yi
			while (Begin < End){//找增广路BFS
l2:				if (god[queue[Begin]] == -1) break;  //X(k) 的邻接点{yi}己被先前结点X(i<k)匹配　　最关键的一步
				for (i = End; i < YSize; ++i){//x(k)抢占{yi},并为X(i<k)重选搭档，从End后的{y}中选取，即从未匹配集{yi}的点中选
l3:					if (chart[ god[ queue[Begin]] ][queue[i]]){
						trace[queue[i]] = god[queue[Begin]];	//按原路扩充交错路　Ｍ　－>　Ｍ',保存在trace
						j = queue[i]; queue[i] = queue[End]; queue[End++] = j;	//X(i<k)重配了End后的{y}中的Yj,则End++,让Yj加入{yi},即加入己匹配队列,避免被重用
					}
				}
				++Begin;
			}
l4:			if (Begin < End){//找到增广路
				i = queue[Begin];
l5:				while (trace[i] != k){//如果X(k)的直接Y(i)还没被匹配则不用回溯,否则回溯重构匹配图
					god[i] = trace[i];
					j = dog[god[i]]; dog[god[i]] = i; i = j; 
				}
				god[i] = k;
				dog[k] = i; 
			}
			else{//d = min{l(x)+l(y)-w(x,y) | x 属于 S,y 属于 T,即x,Y - {y}属于 Ｍ'}
				if (End == YSize)  break;
				int min;
				for (i = End; i < YSize; ++i){
					int d = X[k] + Y[queue[i]] - Weight[k][queue[i]];
					if (i == End || min > d) min = d;
				}
				for (i = 0; i < End; ++i){//在BFS搜索时就可边记录min
					for (j = End; j < YSize; ++j){
					int d = X[ god[queue[i]] ] + Y[queue[j]] - Weight[ god[queue[i]] ][queue[j]];
						if (min > d) min = d;
					}
				}
				for (i = 0; i < End; ++i){//修改顶标
					X[ god[queue[i]] ] -= min;
					Y[queue[i]] += min;
				}
					X[k] -= min;
			}//找不到增广路，降低X(属于S)的顶标，加入新的y 点
		}//while (dog[k] == -1)
		if (dog[k] == -1) return false;
		++k;
	}//while (k < XSize)
	return true;
}

int search()//在abs()前加负号和返回负sum，是求最小权值完美匹配
{
	XSize = MCount;
	YSize = HCount;
	int i, j;
	for (i = 0; i < XSize; ++i)
	   for (j = 0; j < YSize; ++j)
		Weight[i][j] = -Abs(House[j]->x - Man[i]->x) - Abs(House[j]->y - Man[i]->y);
	int sum = 0;
	if (findBestMatch()){
	   for (i = 0; i < XSize; ++i)
		sum += Weight[i][dog[i]];
	}
	return -sum;//返回最小值sum的相反数为最大
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int i, j, m, n;
	char ch;
	for (i = 0; i < SIZE; ++i){
	   Man[i] = (struct Pos*)malloc(sizeof(struct Pos));
	   House[i] = (struct Pos*)malloc(sizeof(struct Pos));
	}
	while (scanf("%d %d", &n, &m), n){
		HCount = 0;
		MCount = 0;
		for (i = 0; i < n; ++i){
			for (j = 0; j < m; ++j){
				scanf(" %c", &ch);
				if (ch == 'H'){
					House[HCount]->x = i;
					House[HCount]->y = j;
					++HCount;     
				}
				else if (ch == 'm'){
					Man[MCount]->x = i;
					Man[MCount]->y = j;
					++MCount;
				}    
			}
		}
		printf("%d\n", search());
	}
	for (i = 0; i < SIZE; ++i){
		free(Man[i]);
		free(House[i]);
	}
	return 0;
}