[NOIP2014]寻找道路

2014的题还真水啊……(会不会被打)

题目(vijos)

这题需要对原图进行重新构造。

首先,存图:因为要解决某个点是否能直接或间接与终点相连,所以我们对原图构一个反向图{e1}。当然,还要有一个原图{e2}。最后,我们还需要一个重构的图{e3},这个重构的图是干嘛用的呢?往后看。

然后,对反向图{e1}从终点开始跑一遍spfa,用以记录哪些点可以直接或间接到达终点,保存在can数组里面。

然后,对{e2}开始重构图:从起点开始重新接边,如果这条边指向的点无法直接或间接到达终点,那么这条边就不加进去。如果可以,那么这条边就加进去。重新构好的图就保存在{e3}。

最后,对{e3}跑一遍spfa。

 

 

发表评论