博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 2060
阅读量:5926 次
发布时间:2019-06-19

本文共 991 字,大约阅读时间需要 3 分钟。

题意:在一个矩形城市里面,有间出租车公司收到翌日的预订行程M个,每个给出起点、终点坐标,两个地点之间的车程就是那两个点之间的曼哈顿距离,车起码要在一个行程的出发时间前一分钟到起点。求最少要多少出租车才够完成所有预订?

分析:每个起点的出发时间是确定的,起点与终点之间的距离也是确定的,因此每个行程的开始和结束的时间地点都是确定的。记A,B是两个行程的起点,A',B'分别是终点,假如由A'到B的时间还在B的规定时间前,那么要走完AA',BB'要用的出租车就只需要一台。把起点与终于合成一个点(这样每个点就是一个行程),若A后能接上B则添加一条有向边<A,B>,把图建好之后,求出最小路径覆盖就是答案。(按照任意两个点A,B之间的时间关系,若有A到B的通路就不可能有B到A的通路,因此图中不会有环。)

PS:按照题意还是有可能存在1→2,2→3,4→2,2→5这种交叉的情况,这样就要用floyd求可达矩阵,但是加上floyd发现TLE了,于是注释掉 floyd,居然就AC了。

View Code
1 #include
2 #include
3 struct point 4 { 5 int departure,arrival; 6 int x0,y0,x1,y1; 7 }; 8 int mat[2][500],nx,ny; 9 bool visited[500],matrix[500][500];10 point p[500];11 int path(int u)12 {13 int i;14 for(i=0;i

以上代码在C++编译器下提交AC,但在GNU C++下提交就CE。提示是

1 F:\temp\11348191.4260\Main.cc: In function 'int manhattan(int, int, int, int)':2 F:\temp\11348191.4260\Main.cc:50: error: 'abs' was not declared in this scope

,什么回事。

转载于:https://www.cnblogs.com/ZShogg/archive/2013/03/14/2959558.html

你可能感兴趣的文章
JFreeChart开发_用JFreeChart增强JSP报表的用户体验
查看>>
SpringMVC+Swagger详细整合
查看>>
计算机视觉领域最全汇总(第2部分)
查看>>
[译] 所有你需要知道的关于完全理解 Node.js 事件循环及其度量
查看>>
(六十九)复合语句
查看>>
我的友情链接
查看>>
Java Web中实现Servlet的方式
查看>>
第三方库之 - SVProgressHUD
查看>>
11个让你吃惊的 Linux 终端命令
查看>>
MySQL与MongoDB的操作对比
查看>>
# 180111php编译错误
查看>>
EIGRP 查看邻居命令详解
查看>>
js闭包
查看>>
度量时间差
查看>>
网络营销与电子商务
查看>>
可输入的模糊搜索ComBox控件
查看>>
MySQL 5.6为什么关闭元数据统计信息自动更新&统计信息收集源代码探索
查看>>
Linux 下mysql永久更改字符集
查看>>
apache prefork模式优化错误
查看>>
jmeter高级用法例子,如何扩展自定义函数
查看>>