# 白雪公主：题解

## 算法与贡献

Codex（GPT-6）推导高度分层的最优边数与构造，实现于 [std.cpp](std.cpp)。同层 DAG 的源汇访问次序采用 [Raghavan 对强连通增广算法的修正](https://terpconnect.umd.edu/~raghavan/preprints/stc.pdf)：从每个源搜索，找到第一个未访问汇时立即停止该次搜索。跨高度的开链、闭链选择和边界处理在下面单独证明。

## 缩点、可行性与代价

先求已有图的强连通分量并缩点。已有边不会上升，所以每个分量内高度相同，缩点图是高度不增的 DAG。若只有一个分量，输出代价0、边数0。

将不同高度排序。任意相邻高度之间都必须有已有下降边跨越；否则新增边也不能从高处向低处跨过这个切分，必然无解。用高度下标上的差分数组在线性边数内检查所有切分。

反之，下述构造证明这个条件足够。设最低、最高高度为 $H_0,H_1$ . 从最低处到最高处必须累计至少 $H_1-H_0$ 的上升，故总代价下界为

$$C=H_1-H_0.$$

构造会让正代价边恰好按高度首尾相接覆盖这个区间，达到下界。

![一条上行边补全下降链](assets/example.svg)

## 最少边数的下界

在高度 $H$ ，记整个缩点图中入度为0的分量数为 $a_H$ 、出度为0的分量数为 $b_H$ ，令 $q_H=\max(a_H,b_H)$ . 孤立分量同时计入两者。

在总代价为 $C$ 时，每个高度间隔恰好被一条正代价新增边跨越。因此这些边的高度区间构成从 $H_0$ 到 $H_1$ 的分割：最低层有一个上升出口，最高层有一个上升入口，每个被选中的中间层各有一个入口和出口。

不作中间停靠的层至少需要 $q_H$ 条同层边；作停靠的层至少需要 $q_H-1$ 条。最低层至少需要 $\max(a_{H_0},b_{H_0}-1)$ 条，最高层至少需要 $\max(a_{H_1}-1,b_{H_1})$ 条。若有 $p$ 条上升边，中间停靠层数就是 $p-1$ ，合计得到

$$
k\ge\sum_H q_H+1-[b_{H_0}>a_{H_0}]-[a_{H_1}>b_{H_1}].
$$

当只有一种高度时，答案退化为标准 DAG 强连通增广的 $\max(a_H,b_H)$ ；单分量已经提前处理。

## 同层的开链过程

只看某一高度的 DAG。来自更高层的已有边终点称为上方入口，通向更低层的已有边起点称为下方出口。全局源、汇则记为集合 $A,B$ .

从 $A$ 中每个源进行 DFS。所有搜索共享已访问标记；一旦遇到第一个未访问的全局汇，就立即结束该源的搜索，并记录一对 $(s_i,t_i)$ . 没有找到汇的搜索会完整扫描它能访问的剩余部分。于是：

- 每个未配对源可以到达一个已配对汇，或一个下方出口。
- 每个未配对汇可从一个已配对源，或一个上方入口到达。

第一条由未成功搜索的结束条件得到；第二条沿未配对汇的逆向路径追溯到局部源：它要么有上方入口，要么是全局源。若该全局源搜索成功，已经配对；若失败却没有经过先前成功的搜索部分，就会访问到这个汇，矛盾。普通点也可分别沿 DAG 向前、向后归约到这些边界。

用同层边 $t_i\to s_{i+1}$ 串起已配对路径。把未配对汇和未配对源尽量一一连接。若还剩源，从主链末端分别连向它们；若还剩汇，从主链末端依次串过它们。这得到起点 $P$ 和终点 $Q$ ，满足 $P$ 可到达 $Q$ ，并且每个局部点都能从 $P$ 或上方入口到达，也都能到达 $Q$ 或下方出口。新增边数恰好为 $q_H-1$ .

若没有配对路径，先连接尽可能多的未配对汇与源。两者数量相等时，没有主链，用了 $q_H$ 条边，所有点均能从上方进入并向下离开；数量不等时，把多出来的一类依次连接，作为 $P$ 到 $Q$ 的主链，仍使用 $q_H-1$ 条边。$a_H=b_H=0$ 时不需要添加任何同层边。

## 何时闭链、何时停靠

中间高度存在主链时，检查加入上述同层边后的两项可达性：

1. 某个上方入口能否到达 $Q$ ；
2. $P$ 能否到达某个下方出口。

若两项都成立，增加 $Q\to P$ 将链闭合，该层不作为上升停靠点。闭合后所有点都能从上方进入并向下离开。否则保持开链，把它作为一个停靠点。闭链花 $q_H$ 条同层边，开链花 $q_H-1$ 条，恰好符合前面的边数下界。

不能把每条开链都无条件选作停靠点。样例4专门覆盖这种错误：同一高度的不同连通部分可能使上升主链无法反向贯通。

最低层没有下方出口。加入一个虚拟源，连向所有上方入口，把它作为第一个搜索源；得到主链末端 $Q$ 作为全局上升链的起点。同层新增边数是 $\max(a_{H_0}+1,b_{H_0})-1=\max(a_{H_0},b_{H_0}-1)$ . 虚拟源不会成为输出边端点。最高层对反图做同样的事，随后反转新增边，得到全局终点，边数为 $\max(a_{H_1}-1,b_{H_1})$ .

最后按高度递增连接各停靠点：上一层的 $Q$ 连向下一层的 $P$ . 正代价总和望远镜相消为 $C$ ，同层边数与停靠数相消，恰好达到 $k$ 的下界。

## 为什么最终强连通

将连接所有停靠点的路径称为上升主链。同层性质说明：任意点可从本层主链起点或更高层进入，并能到达本层主链终点或更低层。沿严格变化的高度继续追溯，最终得到该点与主链之间双向的可达联系。

假设最终仍不强连通。主链本身沿单一方向经过其强连通分量；取其中相邻的两个不同分量，把后者能到达的全部点放在后侧，其余放在前侧。没有后侧到前侧的边，而主链在此被切成前缀和后缀。

若切口在两个不同高度之间，由局部进入、离开性质，较低层全部在前侧、较高层全部在后侧。跨越这个高度间隔的已有下降边就会从后侧通往前侧，矛盾。

若切口位于同一高度 $H$ 的开链内部，则严格低于 $H$ 的点都在前侧，严格高于 $H$ 的点都在后侧。跨越 $H$ 下方间隔的下降边不能从严格高处直接出发，否则已构成后侧到前侧的边；所以它必须从本层前侧出发。局部性质因此迫使 $P$ 能到达一个下方出口。同理，跨越 $H$ 上方间隔的下降边迫使某个上方入口能到达 $Q$ . 两个条件同时成立时算法已经闭链，不会保留这个停靠点，再次矛盾。最低和最高层的主链停靠点各只有一个点，不存在这种内部切口。

因此主链及全部点处于同一强连通分量，构造正确且同时达到两项最优值。

## 复杂度与检验

迭代 Kosaraju、各层 DFS、两次局部可达性搜索及边数差分共 $O(n+m)$ 时间，排序高度 $O(n\log n)$ . 总时间 $O(n\log n+m)$ ，空间 $O(n+m)$ . 不使用可能在50万深链上溢出的递归。

独立检验器用迭代 Tarjan 检查输出后的强连通性、逐边方向、总代价和最优边数；极小图另枚举新增边集合检查最优值。完整上限、无解间隔、孤立点、同层大分量以及必须闭链的情况都进入正式数据。[数据与性能说明](tests/README.md)。