CF1100E题解

FiraCode · 2022-05-02 14:44:08 · 题解

题解思路：

样例：

前置知识：

图中无环的条件是什么？

就是一个点无法走一圈回到自己，他就无环。

那么有一个算法：topsort（拓扑排序）

topsort 就会给每个节点一个拓扑值

图例：

若一个图有环，那么他就没有拓扑序，因为他所有的点的入度都 \ne 0。

若一个点有一个起点终点 \langle u , v\rangle，若 top_{u} < top_{v}，那么这个图就是无环的。

或拓扑排序不能让他的入度为 0，那么他就是有环的。

然后我们来看一下这个题怎么做：

首先他让我们求最大值最小，那么根据经验应该是二分答案。

然后我们就上那方面上想。

把他得到的权值设成 mid \longrightarrow 图中改变方向的边的权值最大值。

我们设 w 为某个点的权值。

我们就先二分答案：

$w > mid$ 按原样加进图。

判定：

若我们把 \le mid 的边都删掉，他还是有环，那么就是删的边数太少了，那么把删边数的多一点。

若没有环了，就让答案的权值小一点。

若我们求出来了一个 mid \longrightarrow 保证图中无环