【二分图+最大匹配】北大 poj 2536 Gopher II

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://poj.org/problem?id=2536
	Name  : 2536 Gopher II

	Date  : Saturday, November 26, 2011
	Time Stage : two hours

	Result: 
9601664	panyanyany
2536
Accepted	200K	32MS	C++
1863B	2011-11-26 21:19:39
9601635	panyanyany
2536
Accepted	200K	47MS	C++
2275B	2011-11-26 21:12:03
9601633	panyanyany
2536
Time Limit Exceeded			C++
2273B	2011-11-26 21:11:47
9601593	panyanyany
2536
Wrong Answer			C++
2190B	2011-11-26 21:01:22
9601586	panyanyany
2536
Wrong Answer			C++
2411B	2011-11-26 20:58:43
9601577	panyanyany
2536
Time Limit Exceeded			C++
2409B	2011-11-26 20:56:27
9601530	panyanyany
2536
Time Limit Exceeded			C++
2188B	2011-11-26 20:41:34
								

Test Data :

Review :
犯了一些比较白痴+神经质的错误, 这题其实是比较简单的……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXSIZE		108

int		n, m, s, v ;
int		link[MAXSIZE] ;
bool	cover[MAXSIZE] ;
bool	graph[MAXSIZE][MAXSIZE] ;

struct POINT {
	double x, y ;
} ;

POINT	gopher[MAXSIZE], hole[MAXSIZE] ;

double dist (int i, int j)
{
	double x = abs (gopher[i].x - hole[j].x) ;
	double y = abs (gopher[i].y - hole[j].y) ;

	return sqrt (x * x + y * y) ;
}

void connect ()
{
	int i, j ;
	memset (graph, 0, sizeof (graph)) ;
	for (i = 1 ; i <= n ; ++i)
	{
		for (j = 1 ; j <= m ; ++j)
		{
			if (dist(i, j) <= s * v)
				graph[i][j] = true ;
		}
	}
}

bool find (int cur)
{
	int i ;
	for (i = 1 ; i <= m ; ++i)
	{
		if (cover[i] == false && graph[cur][i] == true)
		{
			cover[i] = true ;
			if (link[i] == 0 || find (link[i]))
			{
				link[i] = cur ;
				return true ;
			}
		}
	}
	return false ;
}

int getSum ()
{
	int i ;
	int sum ;

	sum = 0 ;
	memset (link, 0, sizeof (link)) ;
	for (i = 1 ; i <= n ; ++i)
	{
		memset (cover, 0, sizeof (cover)) ;
		sum += find (i) ;
	}

	return sum ;
}

int main ()
{
	int i, j ;
	while (scanf ("%d%d%d%d", &n, &m, &s, &v) != EOF)
	{
		// input gopher's coordinates
		for (i = 1 ; i <= n ; ++i)
		{
			scanf ("%lf%lf", &gopher[i].x, &gopher[i].y) ;
		}
		// input gopher hole's coordinates
		for (i = 1 ; i <= m ; ++i)
		{
			scanf ("%lf%lf", &hole[i].x, &hole[i].y) ;
		}

		connect () ;

		printf ("%d\n", n - getSum()) ;
	}
	return 0 ;
}