题意:在一个矩形城市里面,有间出租车公司收到翌日的预订行程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 #include2 #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
,什么回事。