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

?

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL   : http://poj.org/problem?id=2060Name  : 2060 Taxi Cab SchemeDate  : Saturday, December 03, 2011Time Stage : one hourResult: 9622127panyanyany2060Accepted428K219MSC++2003B2011-12-03 16:29:11Test Data :Review :跟 1548 Robots 是差不多的类型，有了经验后，这题就比较简单了，只是还有一点点麻烦而已//----------------------------------------*/#include <stdio.h>#include <string.h>#include <math.h>#define MAXSIZE505intn, m ;intlink[MAXSIZE] ;struct POINT {int x, y ;};// 每次车程的起始时间 t，起点 s, 终点 estruct NODE {POINT s, e ;// s 代表 "start" 开始的意思，e 代表 "end" 结束的意思, int t ;// t 是 "time" 时间的意思} ;NODE map[MAXSIZE] ;boolgraph[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 ;}