题面
给出一个大小为 \(n(1≤n≤10^5)\) 的三角形图（\(n=3\) 时如图），每个方向有 \(n\) 层由有向边构成的路径。可以翻转任意条边的方向，求把让图中每个点都可以到达其他所有点的最小翻转次数。
分析
注意到一个关键点：内部的一排点构成一条路径。这意味着如果外围成环，那么整个图满足条件。因此，我们考虑如何让外围成环即可。
一个外围不能成环的图类似这样（灰色边）：
显然，答案的上界为 \(n\)（\(C-A\) 全部翻转）。考虑找到更少的次数。
观察到连接 \(A,C\) 的边必然有一段翻转，假设是深蓝色部分翻转了，根据上界的限制，一定只会翻转到中间的某个位置，再之后的路就要靠内部已有的边来走了。假设原图内部有一对浅蓝色这样的边，那么就惊喜地发现外围成环了。为了取最优，选择最近的一对即可。
实现上，这等价于找最近的与底边方向不同的边，代码较为简洁。
由于一共有四种翻转深蓝色边的方案，就可以把四种情况相加取 \(\min\) 即可。
接下来大致证明一下这样的最优性。
因为不管是何种构造方式，连接 \(A,C\) 的边必然翻转，即深蓝色边一定是有的，所以只考虑其他内部边走法会不会更优。
绿色边未经翻转
这是上面所讨论的情况。
绿色边经过翻转
蓝色边加绿色边等于 \(n\)，不优。
走红色边
这等价于从 \(C\) 走到 \(D\) 后再做与绿色相同的决策。
如果还想走一半换一条路，绿色边一定是原本就有的，否则蓝加绿为 \(n\)，不优。那么在绿边的起点走更优，肯定不是换路更优。
对于其他奇怪情况，都可以证明其不优，这里不多枚举。
代码较为简洁，故不贴。