[uoj#409][IOI2018]高速公路收费

又是一个傻逼题想了两天,我是真的菜。
设$ask(P)$为只将集合P中边全取B,其余全取A的答案。
首先考虑树咋做。一个显然的做法是静态AAA树上直接暴力搜,理论上次数是$O(\log_2 n)$的,但是我写了两个小时之后发现交上去只有5分。
然后我冷静了一下,发现静态AAA树最多有4倍常数,一个$log$大概是17,$4\times 17=68$,显然会超。
先从简单的情况开始考虑,如果是一棵树且一个点在根的位置。那么可以发现如果直接把边按照bfs序或者dfs序排成序列的话,最后一个改边权之后能让ask结果变化的边即对应着另外一个端点。那么我们可以二分,每次只把改序列的一个后缀全设为B,其他全为A,看ask的结果是否改变。
那么对于一般情况,两个点都不是根,也可以用类似的方法,用dfs序或者bfs序就可以发现最后一个一定是其中一个端点。然后把这个找到的端点作为根,再重新dfs或者bfs。
那么树的情况最多只需要$2\log_2 n$,也就是不超过$2\times 17=34$次。
然后考虑图咋做。首先这个最短路径就可以想到最短路径树,我们发现这个非常好,因为边权全是A的情况下最短路径树和bfs树是等价的。那么就考虑如何利用图的bfs树。
我们发现一个严重的问题就是这棵bfs树上S和T之间的距离可能不是原图中的最短路。要使这是最短路我们需要令根在任意一条S到T的最短路径上。这个怎么找呢?仔细想一下会发现这个限制非常宽,我们考虑分治,用函数$f(P,H)$表示边集$P$中任意一条合法边(需要保证$P$中一定有合法边,且$ask(P\cup H)>ask(\emptyset),ask(H)=ask(\emptyset)$)。
如果$|P|\le 1$直接返回这个元素。
我们把$P$分成两半$P1$和$P2$,formally, $P1\cup P2=P,P1\cap P2=\emptyset,||P1|-|P2||\le 1$。
如果$ask(P1\cup H)>ask(\emptyset)$那么说明$P1$中一定有我们要找的边,所以直接返回$f(P1,H)$即可。
否则说明$P2$中一定有合法元素,我们只需要返回$f(P2,H\cup P1)$。
这样子就可以知道一个合法节点了。
那么我们再回过来考虑bfs树,如果将非树边全部设为B,那么如果最短路径长度不变,那么一定不会去走非树边,那么最短路径长度是否改变仅取决于两者相连的树上路径是否被截断。而之前做树的做法只需要考虑答案是否改变,所以直接套上去即可。
总结一下目前这道题的做法:
Step 1:首先询问$ask(\emptyset)$,需要1次
Step 2:然后找到任意一条在任意一条$S$到$T$最短路径上的边,最多耗费17次。
Step 3:把Step 2中找出来的边的其中一个端点作为根建bfs树,然后将非树边全置为B,树边的bfs序中最后一个能让最短路径改变的边对应着一个端点,我们只需要二分即可。最多耗费17次。
Step 4:用Step 3中找出来的端点用类似方式重新bfs寻找另外一个端点。最多费17次
最差情况可能会有52次。
考虑怎么优化,可以发现,Step 2中我们找到的是边,Step 3中只使用点有点浪费,Step 4中也是类似。先考虑Step 3,我们可以利用一下Step 2找出来的边,设这个边为(x,y)。我们可以把x作为根,优先bfs顶点y,这样这个生成出来的bfs树中y的子树中一定有一个端点,而另外一个端点一定不在y的子树中,所以可以直接两边分开搜,Step 4都不需要执行。
那么最差情况就是分开的两棵树大小相等,就至少减少两次了。那么理论上最差50次,就可以过了。

Tagged with:

发表评论