`

【二分图+最小路径覆盖+注释】北大 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 ;
}
 
0
0
分享到:
评论

相关推荐

    二分图匹配题解1

    求解最小的被吃地鼠数,即求二分图的最大匹配。 5. POJ3041: 这个题目的具体描述不完整,但从题目大意上看,它可能涉及到某种形式的匹配问题,比如工作分配或者任务调度,也可能需要用到二分图最大匹配。 在解决...

    北大POJ部分题目答案(一些基础题目)

    很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    北大acm题解(poj题目分析)

    《北大ACM题解》是一本专为解决POJ(Programming Online Judge)平台上的编程竞赛题目而编写的指导书籍。ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)是一项全球性的比赛,旨在...

    ACM讲课之二分图匹配匈牙利算法学习教案.pptx

    - **有向图最小路径覆盖**:在有向图中寻找覆盖所有顶点的最少路径数。 - **最优匹配(KM算法)**:解决带权重的二分图匹配问题,例如在婚姻匹配问题中寻找最优解。 通过以上内容的学习,可以对二分图匹配及其解决...

    北大POJ经典结题报告

    《北大POJ经典结题报告》是一份针对北京大学在线编程平台POJ的解题报告,旨在帮助学习者掌握算法和编程技巧,提升解决问题的能力。POJ(Problem Online Judge)是北大的一个在线编程竞赛系统,提供了丰富的算法题目...

    北大POJ 大量解题代码

    【标题】"北大POJ大量解题代码"指的是北京大学在线编程平台POJ上的一系列算法题目解决方案的集合。这些代码通常由ACM(国际大学生程序设计竞赛)参赛者或爱好者编写,旨在帮助学习者理解并解决各类算法问题,提高...

    北大poj解题报告

    北京大学在线编程平台POJ(PKU Online Judge)是许多学习算法和进行编程训练的学生们的重要实践场所。这个“北大poj解题报告”包含了作者在使用POJ平台解题过程中的学习总结和经验分享,旨在帮助软件工程专业的学生...

    北京大学poj题目类型分类

    北京大学POJ题目类型分类 北京大学POJ题目类型分类是根据题目的难易程度、知识领域和解决方法对POJ题目进行分类的。通过对POJ题目的分类,可以帮助学习者更好地理解和掌握算法和数据结构的知识。 简单题 简单题是...

    北大POJ初级-图算法

    【北大POJ初级-图算法】是一系列针对北京大学在线编程平台POJ(Problem Online Judge)上的初级编程题目,重点在于图论算法的应用。这个解题报告集合了多种图算法的实现,帮助学习者掌握如何在实际问题中运用这些...

    poj图论题目汇总

    #### 2060 Taxi Cab Scheme - 二分匹配 - **知识点**:二分匹配算法。 #### 2075 Tangled in Cables - 最小生成树 - **知识点**:最小生成树算法。 #### 2112 Optimal Milking - 网络流 - **知识点**:网络流...

    ACM常用算法及其相应的练习题.docx

    * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj2388, poj2299 * 简单...

    北大POJ初级-所有题目AC代码+解题报告

    北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者和学生提供在线编程训练的平台。这个资源集合了北大POJ初级阶段的所有题目,包含已通过(Accepted, AC)的...

    北大poj JAVA源码

    【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...

    北大POJ初级题-数据结构:解题报告+AC代码

    北京大学在线判题系统POJ(Problem Online Judge)是许多编程爱好者和学习者锻炼算法技能的平台,特别是对于初学者,它提供了很多基础题目来帮助理解并应用数据结构。本资源包含的是北大POJ初级题目的解题报告以及...

    POJ算法题目分类

    图算法是指解决图相关问题的算法,包括图的深度优先遍历和广度优先遍历、最短路径算法、最小生成树算法、拓扑排序、二分图的最大匹配等。 * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指...

    北大POJ1159-Palindrome

    北大POJ1159-Palindrome

    北大POJ1837-Balance

    北大POJ1837-Balance

    poj1005.zip_北大poj1005

    【标题】"poj1005.zip_北大poj1005"指的是北京大学(北大)在线编程竞赛平台(POJ,Problem Set)上的第1005号算法问题的压缩包资源。这个压缩包可能包含了该问题的题目描述、输入输出样例、数据限制以及提交代码的...

    ACM 北大POJ二百多道题目解答

    北京大学在线判题系统(PKU Online Judge,简称POJ)是一个为编程爱好者提供在线编程练习的平台,尤其受到ACM/ICPC(国际大学生程序设计竞赛)参赛者们的喜爱。这个压缩包“ACM 北大POJ二百多道题目解答”显然包含了...

Global site tag (gtag.js) - Google Analytics