白雪公主：题解¶
算法与贡献¶
Codex（GPT-6）推导高度分层的最优边数与构造，实现于 std.cpp。同层 DAG 的源汇访问次序采用 Raghavan 对强连通增广算法的修正：从每个源搜索，找到第一个未访问汇时立即停止该次搜索。跨高度的开链、闭链选择和边界处理在下面单独证明。
缩点、可行性与代价¶
先求已有图的强连通分量并缩点。已有边不会上升，所以每个分量内高度相同，缩点图是高度不增的 DAG。若只有一个分量，输出代价0、边数0。
将不同高度排序。任意相邻高度之间都必须有已有下降边跨越；否则新增边也不能从高处向低处跨过这个切分，必然无解。用高度下标上的差分数组在线性边数内检查所有切分。
反之，下述构造证明这个条件足够。设最低、最高高度为 \(H_0,H_1\) . 从最低处到最高处必须累计至少 \(H_1-H_0\) 的上升，故总代价下界为
构造会让正代价边恰好按高度首尾相接覆盖这个区间，达到下界。
最少边数的下界¶
在高度 \(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\) ，合计得到
当只有一种高度时，答案退化为标准 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\) 时不需要添加任何同层边。
何时闭链、何时停靠¶
中间高度存在主链时，检查加入上述同层边后的两项可达性：
- 某个上方入口能否到达 \(Q\) ；
- \(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 检查输出后的强连通性、逐边方向、总代价和最优边数；极小图另枚举新增边集合检查最优值。完整上限、无解间隔、孤立点、同层大分量以及必须闭链的情况都进入正式数据。数据与性能说明。