ACM-ICPC 2018 world final A题 Catch the Plane

阅读量：5126 次

发布时间：2019-06-13

本文共 8890 字，大约阅读时间需要 29 分钟。

题目连接：https://icpc.kattis.com/problems/catch

Catch the Plane

Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus. Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the probability of catching your plane.

You have a detailed map of the city, which includes all the bus stations. You are at station 0

If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time whether a given bus will run as planned – you will find out only when you try to get on the bus. So if two or more buses leave a station at the same time, you can try to get on only one of them.

$\includegraphics[width=0.5\textwidth ]{catch2}$

Figure 1: Bus schedule corresponding to Sample Input 1.

Consider the bus schedule shown in Figure 1. It lists the start and destination stations of several bus routes along with the departure and arrival times. You have written next to some of these the probability that that route will run. Bus routes with no probability written next to them have a 100%

Input

The first line of input contains two integers m

Each of the next m

Output

Display the probability that you will catch your plane, assuming you follow an optimal course of action. Your answer must be correct to within an absolute error of 10−6

Sample Input 1	Sample Output 1
8 410000 1 0 900 0.20 2 100 500 1.02 1 500 700 1.02 1 501 701 0.10 3 200 400 0.53 1 500 800 0.13 0 550 650 0.90 1 700 900 0.1	0.3124

Sample Input 2	Sample Output 2
4 220 1 0 1 0.50 1 0 1 0.50 1 1 2 0.40 1 1 2 0.2	0.7

Icpc2018 题目A：赶飞机

你乘坐的去ICPC总决赛的飞机很快就要起飞了，前往机场的唯一方式是乘坐公交车。不幸的是，一些公交车司机正在考虑罢工，所以你不知道能否按时到达机场。你的目标是规划路线使赶上飞机的可能性最大化。

你有一份标有所有公交车站的这座城市的详细地图。你在0站，机场在1站。你也有一份完整的每辆公交车出发时间和到达时间的计划表。除此之外，知道每辆公交车实际按照计划表运行的可能性，而不是司机罢工的可能性。假设所有事件相互独立，也就是说，如果知道任何其他公交车是否按计划运行，则给定公交车按计划运行的概率不会改变。

如果你能在公交车离开之前到达，就能换乘该公交车。但是如果你正好的公交车离开的时间到达则没有足够的时间上车。你无法提前验证给定的公交车是否按计划运行—只有当尝试上车时才会发现。所以当有两辆或更多公交车同时离开公交站，你只能尝试上其中一辆车。

公交车时间表
起始站	目的站	离开时间	到达时间
0	1	0(20%)	900
0	2	100	500
2	1	500	700
2	1	501(10%)	701
0	3	200(50%)	400
3	1	500(10%)	800
3	0	550(90%)	650
0	1	700(10%)	900

表 A.1：对应样例输入1的公交时间表

考虑图A.1中所示的公交时刻表。它列出了几条公交线路的起点和终点站以及出发和到达时间。你已经在其中一些中写下了该路线运行的概率。没有写在他们旁边的概率的公交车路线有100％的运行机会。你可以尝试追上第一个列出的公共汽车。如果它运行，它会带你直接去机场，你可以不用担心。如果没有，事情变得更加棘手。你可以乘坐第二辆列车前往2号站。它肯定会离开，但是你赶不上第三辆列出的公共汽车，否则它会按时送你到机场。第四个列出的公共汽车可以追上但只有0.1的实际运行概率。这是一个糟糕的赌注，所以最好留在0号站并等待第五辆列出的公交车。如果你赶上它，你可以尝试乘坐第六辆到达机场的列车;如果没有运行，你仍然有机会返回0号站并将最后一辆列出的公共汽车直接送往机场。

输入：

第一行输入两个整数m,n（1=<m<=10^6,2=<n<=10^6）, 表示公共汽车的数量和城市的车站数量.接下来的一行一个整数k（1=<k<=10^18），表示你必须达到机场的时间。

接下来的m行中的每一行都描述一辆公交车。每行包括整数a和b（0=<a,b<n,a!=b）,表示该公交的起始站和终点站。接下来是整数s和t（0=<s<t<k）,给定从站点a的离开时间和到达站点b的时间。最后一行是p（0=<p<=1，最多精确到小数点后10位），表示公交车按计划运行的概率。

输出：

假设你遵循最佳行动方案，表示你将赶上你的飞机的概率。你的答案必须正确，绝对误差为10^-6。

理解题意

给定一系列的公交车，在本报告中对其编号（从1到M），可以乘坐任何公交前往飞机场，但其中有如下限制与难点：

公交车出发的是有概率的，记为P。有P的可能性开车，有（1-P）的可能性不开车。

若要换乘公交车，上一辆的到达时间一定要早于下一辆的出发时间。

求出到达飞机场的最大概率。也就是说，在有多种选择的情况下，要选取概率最高的路线。在该路线概率最大的情况下，其子路线肯定也是概率最大的，这就引出了动态规划算法。

题目数据量很大，k的范围是[1,10^18]，所以C++需要用long long。

给出的公交车很多，甚至有时间超过k的，相同站点和时间的，要想百分百AC，这些细节需要把握。

现在开始分析样例，见下面的手绘图，其中左图的①②③……为输入样例中的公交车标号；后面的五个数字为该车的信息（出发站，目的站，出发时间，到达时间，开车概率）。右边的树状图为分析图，①②③……表示使用该公交车；左右孩子中的左分支表示开车（并带有开车的概率），右分支表示不开车（并带有不开车的概率）；☆为到达终点（并带有该路线下的总概率）；在有多种选择的情况下，要选取概率最高的路线作为子路线。

样例2的图解：选择公交车①，开车概率为0.5，可直接到达飞机场，总概率0.5。公交车①不开车的概率为0.5，此情况下，可以选择两种路线，选择公交车③，有0.4的概率开车并到达飞机场，该路线的总概率为0.5*0.4=0.2；选择公交车④，有0.2的概率开车并到达飞机场，该路线的总概率为0.5*0.2=0.1；选择最优子结果，即概率为0.2的线路。最终总概率为0.5+0.2=0.7。

样例1的图解：选择公交车①，开车概率为0.2，可直接到达飞机场，总概率为0.2。公交车①不开车的概率为0.8，存在两种路线，两种路线按照上面一样的分析方法，左孩子的路线概率为0.8*1.0*0.1=0.08；右孩子的路线概率为0.5*0.1+0.5*0.9*0.9*0.1+0.5*0.1=0.1124；选择概率大的路线，即0.1124。最终总概率为0.2+0.1124=0.3124。

设计算法

既然分析出了需要动态规划，就需要设计状态转移方程。要计算从车站0到飞机场的概率，那么对应上图（第三节的两张手绘图）的树该如何构造和求解呢？

首先就要扫描所有可能的公交车。因为要构造的是树，只有已知整条路径的概率才能得到总概率，所以需要从下到上构造树。为了能从下到上构造，那么就需要从飞机场开始往回倒推DP，做法是：按照开车时间逆序来扫描所有的公交车，这样就能正确地更新父节点的概率值。

计算概率值。已知公交车的扫描顺序，那么就需要计算对应节点的概率值。每个公交车都有开车和不开车两种情况，所以分两种情况累加概率值。由于车况复杂，每种情况可能都有各自的子结构，为了最大化概率，选择最优子结构，以此完成DP的概率计算。

经过以上分析，DP状态转移方程如下：

dp[node]=P*dp[destination]+(1-P)*dp[start]

dp[node]=max(dp[node], dp[child1], dp[child2], dp[child3], …)

数据结构的设计与解释：Bus结构体对应了树的节点如下，包括起始站、终点站、开车时间、到达时间、开车概率、路线总概率。其中的运算符重载保证了sort()函数排序的有效性。自写的cmp函数保证了公交车的扫描顺序为开车时间的逆序。

数据结构建好之后，为了优化空间，不直接建立树结构，而是按照时间从后往前更新，保证树结构的正确性即可。需要更新的值就是结构体中的value，伪代码如下所示：

//伪代码：

vector<Bus> buses;

输入数据cin>>buses;

sort(buses);

//DP

maxProbablity = 0

for bus in buses://时间逆序扫描

if 时间合法

if 不开车的DP

value += (1-P)*dp[start];

if 开车的DP

value += P*dp[destination]

//该节点更新成最大概率值

value = max(value, buses.value)

//根节点更新成最大概率值

if value == 起点：

maxProbablity = max(maxProbablity, value)

return maxProbablity

/*提交链接：https://icpc.kattis.com/problems/catch运行时间：2.35占用内存：3158bytes*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;struct Bus{    int start, destination;//起始站，终点站    long long departure, arrival;//开车时间，到达时间    double P, value;//开车概率，树中该节点到达飞机场的总概率值    bool operator<(const Bus& bus) const    {   //优先按照按照起始站站号排正序，再按照开车时间排正序        if (start != bus.start) return  start< bus.start;        return departure < bus.departure;    }};bool cmp(pair
          
            A, pair
           
             B){ //先按起始时间排逆序，再按车号排逆序 if(A.first!=B.first) return A.first>B.first; return A.second>B.second;}int main(){ int M, N; long long K; while (cin >> M >> N >> K) { //公交车结构体数组 vector
            
              buses(M+1); for (int i = 0; i < M; i++) { cin >> buses[i].start >> buses[i].destination >> buses[i].departure >> buses[i].arrival >> buses[i].P; buses[i].value = 0.0; } //将飞机场信息加入公交车数组 buses[M].start = 1; buses[M].departure = K+1; buses[M].value = 1.0; sort(buses.begin(), buses.end()); //车号数组，方便找到车号。 vector
             
              
                > orders(M+1); //开车时间，车号 for (int i = 0; i <= M; i++) orders[i] = make_pair(buses[i].departure, i); sort(orders.begin(), orders.end(), cmp); //符号为了排序方便。假设没有符号。先按起始时间排逆序，再按车号排逆序 //开始DP求概率 double maxProbablity = 0.0; for (int i = 0; i <= M; i++) if (orders[i].first <= K) //出发时间在限制之内 { int number = orders[i].second; //车号 Bus& r = buses[number]; r.value = 0.0; //不开车 Bus r2; r2.start = r.start; r2.departure = r.departure; vector
               
                ::iterator it = upper_bound(buses.begin(), buses.end(), r2); if (it != buses.end() && it->start == r.start) //可以选择这个车 r.value += (1.0-r.P) * it->value; // 错过这班车 //开车 r2.start = r.destination; r2.departure = r.arrival; it = upper_bound(buses.begin(), buses.end(), r2); if (it != buses.end() && it->start == r.destination) //可以选择这个车 r.value += r.P * it->value; // 赶上了这班车 //在所有子结构中，更新出最大概率 if (number < M && buses[number+1].start == buses[number].start) r.value = max(r.value, buses[number+1].value); //该站是0，更新结果 if (r.start == 0) maxProbablity = max(maxProbablity, r.value); } printf("%0.10lf\n", maxProbablity); }}