going home(带权二分匹配km o(n^4)).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <cstdlib>
#include <string>
#include <queue>
#include <algorithm> 
using namespace std; 

const int NMAX = 310; 

bool map[NMAX][NMAX];	// equi-subgraph, map[i][j] = true : i -> j
bool tx[NMAX], ty[NMAX];// mark augmented path
int lx[NMAX], ly[NMAX];	// lable of xi,yi
int match[NMAX];		// match[y] = x : y be matched by x
int w[NMAX][NMAX], n;	// w[i][j]
int pw, ph;
char path[NMAX][NMAX];

bool dfs(int pos) 
{ 
	int i;
	for(i=0; i < n ;i++) { 
		if(!ty[i] && map[pos][i]) { 
			ty[i] = true;
			int pre = match[i];
			match[i] = pos;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			match[i] = pre;
			if(match[i] != -1) {
				tx[ match[i] ] = true;
			}
		}
	}
	return false;
}

int KM_Perfect_Match() 
{
	int i, j;
	// L(x) = max{ W(x,y) }, L(y) = 0
	for(i=0; i < n ;i++) {
		lx[i] = INT_MIN;
		ly[i] = 0;
		for(j=0; j < n ;j++) {
			lx[i] = max(lx[i], w[i][j]);
		}
	}

	bool perfect = false;
	while(!perfect) {
		// refresh equi-subgraph
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++) {
				if(lx[i]+ly[j] == w[i][j]) {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			} 
		}
		// matching，find augmented path and mark
		int max_match = 0;
		memset(match, -1, sizeof(match));
		for(i=0; i < n ;i++) { 
			memset(tx, false, sizeof(tx)); 
			memset(ty, false, sizeof(ty)); 
			if( dfs(i) ) {
				max_match ++;
			}
			else {
				tx[i] = true;
				break;
			}
		}
		if(max_match == n) {
			perfect = true;
		}
		else {
			// refresh lable
			// ex = min{ L(x)+L(y)-W(x,y) | x∈S , y∈~T }
			int ex = INT_MAX;
			for(i=0; i < n ;i++) {
				for(j=0; tx[i] && j < n ;j++) {
					if(!ty[j]) {
						ex = min(ex, lx[i]+ly[j]-w[i][j]);
					}
				}
			}
			for(i=0; i < n ;i++) {
				if(tx[i]) {
					lx[i] -= ex;
				}
				if(ty[i]) {
					ly[i] += ex;
				}
			}
		}
	}
	// cost : maxinum weight match
	// cost : mininum cost cover
	int cost = 0;
	for(i=0; i < n ;i++) { 
		cost += w[ match[i] ][i]; 
	}
	return cost;
}


struct node {
	int x,y;
};
node boy[NMAX], house[NMAX];

void make_graph()
{
	int i,j;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++) {
			w[i][j] = abs( boy[i].x-house[j].x ) + abs( boy[i].y-house[j].y );
			w[i][j] = - w[i][j];
		}
	}
}

int main() 
{  
	int i, j, m;

	while(scanf("%d %d", &ph, &pw)==2) {
		if(ph == 0 && pw == 0) {
			break;
		}
		memset(w, 0, sizeof(w));
		n = 0;	m = 0;
		getchar();
		for(i=0; i < ph ;i++) {
			gets(path[i]);
			for(j=0; j < pw ;j++) {
				if(path[i][j] == 'm') {
					boy[n].x = i;
					boy[n].y = j;
					n ++;
				}
				else if(path[i][j] == 'H') {
					house[m].x = i;
					house[m].y = j;
					m ++;
				}
			}
		}//read data
		make_graph();
		printf("%d\n", -KM_Perfect_Match());
	}
	return 0; 
}