Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码有点长,但是感觉思路还行,1A,贴下留念~~~

Posted by yangzefeng at 2012-12-03 21:47:12 on Problem 2195
#include<iostream>
#include<queue>

using namespace std;

#define MAX 101
#define INF (1 << 31 - 1)

struct TM
{
	int x;
	int y;
}; 
struct TH
{
	int x;
	int y;
};
struct TNode
{
	int x;
	int y;
	int step;
};
TM tms[MAX];
TH ths[MAX];
int map[MAX][MAX];
int rows, cols;
int cntM, cntH;
int xx[4] = {0, 1, 0, -1};
int yy[4] = {-1, 0, 1, 0};
bool vis[MAX][MAX];
queue<TNode> qq;

void vInput()
{
	int i, j;
	char ch;

	cntM = 0, cntH = 0;
	for(i = 1; i <= rows; i++)
	{
		getchar();
		for(j = 1; j <= cols; j++)
		{
			scanf("%c", &ch);
			if(ch == 'm')
			{
				tms[++cntM].x = i;
				tms[cntM].y = j;
			}
			else if(ch == 'H')
			{
				ths[++cntH].x = i;
				ths[cntH].y = j;
			}
		}
	}
}

bool inmap(int x, int y)
{
	if(x > 0 && x <= rows && y > 0 && y <= cols)
		return true;
	return false;
}

int bfs(int start, int end)
{
	int i, nx, ny;
	TNode cur, temp;

	cur.x = tms[start].x;
	cur.y = tms[start].y;
	cur.step = 0;

	memset(vis, false, sizeof(vis));
	while(!qq.empty())
		qq.pop();

	qq.push(cur);
	vis[cur.x][cur.y] = true;
	while(!qq.empty())
	{
		cur = qq.front();
		qq.pop();

		if(cur.x == ths[end].x && cur.y == ths[end].y)
			return cur.step;

		for(i = 0; i < 4; i++)
		{
			nx = cur.x + xx[i];
			ny = cur.y + yy[i];
			if(!vis[nx][ny] && inmap(nx, ny))
			{
				temp.x = nx;
				temp.y = ny;
				temp.step = cur.step + 1;
				qq.push(temp);
				vis[nx][ny] = true;
			}
		}
	}

	return -1;
}

void vBuiltMap()
{
	int i, j;

	for(i = 1; i <= cntM; i++)
		for(j = 1; j <= cntH; j++)
		{
			map[i][j] = bfs(i, j);
		}
}

int lx[MAX], ly[MAX];
bool markx[MAX], marky[MAX];
int link[MAX];

bool bHungarian(int u)
{
	int v;

	markx[u] = true;

	for(v = 1; v <= cntH; v++)
	{
		if(!marky[v] && lx[u] + ly[v] == map[u][v])
		{
			marky[v] = true;
			if(link[v] == 0 || bHungarian(link[v]))
			{
				link[v] = u;
				return true;
			}
		}
	}
	return false;
}

int nKM(bool isMAX)
{
	int i, j, k, dd, sum;

	memset(link, 0, sizeof(link));
	memset(ly, 0, sizeof(ly));//初始化为0

	if(!isMAX)
	{
		for(i = 1; i <= cntM; i++)
			for(j = 1; j <= cntH; j++)
				map[i][j] *= -1;
	}

	for(i = 1; i <= cntM; i++)
	{
		lx[i] = -INF;
		for(j = 1; j <= cntH; j++)
		{
			if(lx[i] < map[i][j])
				lx[i] = map[i][j];
		}
	}

	for(i = 1; i <= cntM; i++)
	{
		while(1)
		{
			memset(markx, false, sizeof(markx));
			memset(marky, false, sizeof(marky));

			if(bHungarian(i))
				break;

			dd = INF;
			for(j = 1; j <= cntM; j++)
			{
				if(markx[j])
				{
					for(k = 1; k <= cntH; k++)
					{
						if(!marky[k])
							if(dd > (lx[j] + ly[k] - map[j][k]))
								dd = lx[j] + ly[k] - map[j][k];
					}
				}
			}

			for(j = 1; j <= cntM; j++)
			{
				if(markx[j])
					lx[j] -= dd;
				if(marky[j])
					ly[j] += dd;
			}
		}
	}

	sum = 0;
	for(i = 1; i <= cntH; i++)
	{
		sum += map[link[i]][i];
	}

	return -sum;
}

void vOut(int nOut)
{
	printf("%d\n", nOut);
}

int main()
{
	int nAns;

	while(2 == scanf("%d%d", &rows, &cols))
	{
		if(rows == 0 && cols == 0)
			break;
		vInput();
		vBuiltMap();
		nAns = nKM(false);
		vOut(nAns);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator