题解 P4865 【Samcompu Loves Water】
这道题就是一并查集板子题..
如果没有失效的跳转方式的话,我们可以直接把所有的跳转方式按照危险程度排个序,然后一个一个按照并查集的方式加边,方案数的话就直接每次拿要合并的联通块的size的乘积加上去就好了..至于答案,先离线按照时间排个序,在加边前如果危险程度大于时间就直接把当前的总方案数*2(因为A->B和B->A算两种答案)当成答案就好了.
加上失效的跳转方式怎么办呢??
出题人非常良心的强调了不同的
所以就可以把这些可能失效的跳转方式专门拿出来,处理一个询问时就先备份好之前的数组,然后暴力加上需要加上的边,记录答案后就直接恢复原数组就好了..
代码