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

为什么不能过?求大牛解答!!!

Posted by likit at 2010-01-26 12:47:50 on Problem 2195
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>

using namespace std;

#define  Max( x, y ) ( ((x) > (y)) ? (x) : (y) )
#define  Min( x, y ) ( ((x) < (y)) ? (x) : (y) )
#define oo 2147483647

struct pt
{
	int x,y;
	pt()
	{
		x = y = 0;
	}
};

int mat[555][555],m,n;
pt man[555],h[555];
int numofm,numofh;

int w[555][555],visitedx[555],visitedy[555],match[555];
int lx[555],ly[555];

void init()
{
	for(int i = 0;i < numofm;i++)
		for(int j = 0;j < numofh;j++)
			w[i][j] = abs(man[i].x - h[j].x) + abs(man[i].y - h[j].y);
}

bool path(int u)
{
	visitedx[u] = 1;
	for(int v = 0;v < numofh;v++)
	{
		if(!visitedy[v] && lx[u] + ly[v] == w[u][v])
		{
			visitedy[v] = 1;
			if(match[v] == -1 || path(match[v]))
			{
				match[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

void solve()
{
	init();
	for(int i = 0;i < numofm;i++)
		for(int j = 0;j < numofh;j++)
			w[i][j] = -w[i][j];

	for(int i = 0;i < numofm;i++)
	{
		ly[i] = 0;
		lx[i] = -oo;
		for(int j = 0;j < numofh;j++)
			lx[i] = Max(lx[i],w[i][j]);
	}

	memset(match,-1,sizeof(match));

	for(int u = 0;u < numofm;u++)
	{
		while(1)
		{
			memset(visitedx,0,sizeof(visitedx));memset(visitedy,0,sizeof(visitedy));
			if(path(u))	break;

			int dx = oo;
			for(int i = 0;i < numofm;i++)
				if(visitedx[i])
					for(int j = 0;j < numofh;j++)
						if(!visitedy[j])
							dx = Min(dx,lx[i] + ly[j] - w[i][j]);


			for(int i = 0;i < numofm;i++)
			{
				if(visitedx[i])	lx[i] -= dx;
				if(visitedy[i])	ly[i] += dx;
			}
		}
	}

	int ans = 0;
	for(int i = 0;i < numofh;i++)
		ans += w[match[i]][i];
	ans = -ans;
	cout<<ans<<endl;
}

int main()
{
	while(cin>>n>>m)
	{
		if(n == 0 && m == 0)	break;
		memset(mat,0,sizeof(mat));memset(lx,0,sizeof(lx));memset(ly,0,sizeof(ly));memset(w,0,sizeof(w));
		numofm = numofh = 0;
		for(int i = 0;i < n;i++)
		{
			fflush(stdin);
			for(int j = 0;j < m;j++)
			{
				char ch;cin>>ch;
				if(ch == 'm')
				{
					man[numofm].x = i;
					man[numofm].y = j;
					numofm++;
				}
				if(ch == 'H')
				{
					h[numofh].x = i;
					h[numofh].y = j;
					numofh++;
				}
			}
		}
		solve();
	}
	
	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