Skip to content
Ficon's Paper
Go back

CF1777E

我们对边的最大权重值 C 进行二分,题目也就变成了:在边权小于等于 C 的边全部变成双向边时,是否存在一个节点能够到达所有的点。

通过 Kosaraju 我们可以知道,在进行第一遍 DFS 结束后,post_order 的最后一个点就是源点,我们只需要判断这个点能否到达所有点即可,可以通过检查遍历点的数量实现。

至于条件双向边的存储,可以使用邻接链表,链表内存一个结构体,存有这个边的目标点是什么,是不是反向边,边权是多少。当它是正向边时,它一定可以走,当它是反向边时,只有边权小于等于当前的检查值才可以走。

时间复杂度 O(n+m)logCO(n + m)\cdot \log C


Share this post on:

Previous Post
CF2181D
Next Post
CF1777D