题解：P15950 [JOI Final 2026] 电压 2 / Voltage 2

ArSGTExp · 2026-04-28 14:10:46 · 题解

被骗了 1h。/ll

先转化电阻器为有向边。以下填涂方案中未提到的点均默认填 0。

你分析题目发现不了任何可以处理复杂情况的性质，于是猜测较复杂的情况都是无解，发现如果图上存在环那么一定无解（反向环上所有边，任意询问显然结果不变）。

于是你有解的东西是个 dag。那么现在我们可以干的事情就是拓扑，把处理过的点全部标记为 1，这样我们只要依次查询把一个未处理的点标记为 1 的图就可以找到入度为 0 的点，这样你这里的询问次数是 n^2 的。

我们可以在找到入度 0 的点 t 时找 t 的所有入边。假设现在要确认 p \rightarrow t 是否有边，我们标记此时所有未处理点为 1，标记 p 为 1，分别查询 t 为 0, 1 的时候的温度大小关系，这样这里可以 n 次确认一个点的入边。

现在总次数是平方的，非常的不好，我们考虑优化。我们发现对于一个 0 入度点 p 和一个任意点拓扑序均大于 p 的点集 S 我们可以一次确认 p 是否和 S 中任意一点有边连接，具体的，我们把已完成点集 T 设置为全 0，未完成点集除去 S 的部分 V 设置为全 1，S 设置全 0，两个图的 p 分别设为 0, 1，若有变化就是有边。

那么我们考虑找到一个 0 入度点后，对剩余点集分治找出其所有出边终点，对于每个出边终点判断其是否 0 入度加队列即可，分治层次数 m \log n，拓扑层复杂度 O(\sum d) = O(m)。

这题 lg 测不了，不挂 code。