【二分图+最小路径覆盖+注释】北大 poj 2060 Taxi Cab Scheme

 

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

	URL   : http://poj.org/problem?id=2060
	Name  : 2060 Taxi Cab Scheme

	Date  : Saturday, December 03, 2011
	Time Stage : one hour

	Result: 
9622127	panyanyany
2060
Accepted	428K	219MS	C++
2003B	2011-12-03 16:29:11

Test Data :

Review :
跟 1548 Robots 是差不多的类型，有了经验后，这题就比较简单了，只是还有一点点麻烦而已
//----------------------------------------------------------------------------*/

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

#define MAXSIZE	505

int		n, m ;
int		link[MAXSIZE] ;

struct POINT {
	int x, y ;
};

// 每次车程的起始时间 t，起点 s, 终点 e
struct NODE {
	POINT s, e ;	// s 代表 "start" 开始的意思，e 代表 "end" 结束的意思, 
	int t ;			// t 是 "time" 时间的意思
} ;
NODE 	map[MAXSIZE] ;
bool	graph[MAXSIZE][MAXSIZE], cover[MAXSIZE] ;

// 求两点距离
inline int dist (POINT a, POINT b)
{
	return abs (a.x - b.x) + abs (a.y - b.y) ;
}

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

int main( )
{
	int i, j ;
	int ho, mi ;
	int sum ;
	while (~scanf ("%d", &n))
	{
		while (n--)
		{
			scanf ("%d", &m) ;
			for (i = 0 ; i < m ; ++i)
			{
				scanf ("%d:%d %d %d %d %d", &ho, &mi, &map[i].s.x, &map[i].s.y,
					&map[i].e.x, &map[i].e.y) ;
				map[i].t = ho * 60 + mi ;		// 将时间都化为分钟
			}

			memset (graph, false, sizeof (graph)) ;
			for (i = 0 ; i < m ; ++i)
			{
				for (j = 0 ; j < m ; ++j)
				{
					// 此次车程结束所花时间为 
					// map[i].t + dist(map[i].s, map[i].e)
					// 从此次车程的终点 到 下一次车程的起点 所花时间为：
					// dist(map[i].e, map[j].s)
					// 两者相加的和 必须 小于 map[j].t 第二次车程的超始时间，
					// 如此下一个乘客才能顺利搭上车
					if ((i != j) &&
						((map[i].t + 
						 dist(map[i].s, map[i].e) + 
						 dist(map[i].e, map[j].s)) < map[j].t))
					{
						graph[i][j] = true ;
//						printf ("%d, %d, true\n", i, j) ;
					}
// 					else
// 						printf ("%d, %d, %d >= %d\n", i, j, (map[i].t + 
// 						dist(map[i].s, map[i].e) + 
// 						dist(map[i].e, map[j].s)), map[j].t) ;
				}
			}

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

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