POJ-2195 Going Home

POJ-2195 Going Home.cpp

//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int size = 160;
const int INF = 1000000000;

typedef struct pos{
	int x, y;
} pos;

bool map[size][size];
bool xckd[size], yckd[size];
int match[size];
pos peo[size], house[size];

bool DFS(int ,const int);

void KM_Perfect_Match(const int n, const int edge[][size])
{
	int i, j;
	int lx[size], ly[size];
	for(i = 0; i < n; i++)
	{
		lx[i] = -INF;
		ly[i] = 0;
		for(j = 0; j < n; j++)
			lx[i] = max(lx[i], edge[i][j]);
	}
	bool perfect = false;
	while(!perfect)
	{
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(lx[i] + ly[j] == edge[i][j])
					map[i][j] = true;
				else
					map[i][j] = false;
		int live = 0;
		memset(match, -1, sizeof(match));
		for(i = 0; i < n; i++)
		{
			memset(xckd, false, sizeof(xckd));
			memset(yckd, false, sizeof(yckd));
			if(DFS(i, n)) live++;
			else
			{
				xckd[i] = true;
				break;
			}
		}
		if(live == n) perfect = true;
		else
		{
			int ex = INF;
			for(i = 0; i < n; i++)
				for(j = 0; xckd[i] && j < n; j++)
					if(!yckd[j]) ex = min(ex, lx[i] + ly[j] - edge[i][j]);
			for(i = 0; i < n; i++)
			{
				if(xckd[i]) lx[i] -= ex;
				if(yckd[i]) ly[i] += ex;
			}
		}
	}
}

bool DFS(int p, const int n)
{
	int i;
	for(i = 0; i < n; i++)
	{
		if(!yckd[i] && map[p][i])
		{
			yckd[i] = true;
			int t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t, n))
				return true;
			match[i] = t;
			if(t != -1) xckd[t] = true;
		}
	}
	return false;
}

int main()
{
	int n, m, edge[size][size], peonum, housenum;
	char s[150];
	while(scanf("%d%d", &n, &m) != EOF && n && m)
	{
		peonum = housenum = 0;
		for(int i = 0; i < n; i++)
		{
			scanf("%s", s);
			for(int j = 0; j < m; j++)
			{
				if(s[j] == 'H')
				{
					peo[peonum].x = i;
					peo[peonum].y = j;
					peonum ++;
				}	
				if(s[j] == 'm')
				{
					house[housenum].x = i;
					house[housenum].y = j;
					housenum ++;
				}
			}
		}
		for(int i = 0; i < peonum; i++)
			for(int j = 0; j < peonum; j++)
			{
				edge[i][j] = 0 - abs(peo[i].x - house[j].x) - abs(peo[i].y - house[j].y); 
			}
		KM_Perfect_Match(peonum, edge);
		int cost = 0;
		for(int i = 0; i < peonum; i++)
			cost += edge[match[i]][i];
		printf("%d\n", - cost);
	}
	return 0;
}