题目分析

我们有两个有向路径图（每条河边的城市形成一条有向链），以及若干条待定向的跨边。需要为这些跨边选择方向，使得最终图的某个拓扑性质最优。

---

核心概念重述

1. 连通性定义

题目中的“连通”特指强连通（双向可达），即两个顶点在同一个强连通分量中。

2. 权值的组合意义

权值定义为：最大的顶点集合，使得其中任意两个顶点都不在同一个SCC中。

关键洞察：这个权值等于在SCC缩点后的DAG中，点权和最重的链的长度，其中每个SCC的权值就是它包含的原始顶点数。

证明思路：

• 在DAG中，一条链上的不同SCC之间可能有单向路径，但绝不可能双向可达
• 因此可以从链上的每个SCC中各取一个顶点，这些顶点两两不连通
• 要最大化这个集合，自然就是找点权和最大的链

---

问题重构

目标：通过为跨边定向，最小化SCC缩点后DAG的最长点权链。

---

图结构特性分析

初始状态分析

不加跨边时：

• 每个顶点自成一个SCC
• DAG就是两条有向链
• 最长链点权和 = a + b

跨边的作用机制

跨边可以合并SCC，从而：

1. 减少DAG中的节点数
2. 可能改变DAG的链结构
3. 最终影响最长链的点权和

最优解的性质

最优解通常对应于将顶点划分成尽可能少的SCC，且这些SCC在DAG中形成宽度较大的结构，而不是长长的链。

---

算法框架

阶段一：SCC合并规划

将问题视为在无向跨边图上规划SCC的合并：

1. 构建无向图 $G_u$，顶点为所有城市，边为跨边
2. 在 $G_u$ 的每个连通分量中，我们可以通过合适的定向，使该分量中的所有顶点强连通
3. 但需注意：两条河的有向链结构可能限制合并能力

阶段二：定向策略

对于每条跨边 $(u, v)$ 的定向选择：

• 保守策略：选择不产生环的方向
• 激进策略：选择能合并更多SCC的方向

实际采用贪心合并：

• 维护SCC的DAG结构
• 对于跨边，选择能合并SCC且不违反DAG性质的方向
• 使用并查集维护SCC关系

阶段三：权值计算

最终图的权值计算：

1. 对定向后的图求SCC
2. 构建缩点DAG
3. 拓扑排序 + DP 求最长点权链

---

关键技术细节

1. 高效SCC计算

使用Tarjan或Kosaraju算法，复杂度 $O(n + m)$

2. DAG最长链DP

状态转移：

dp[v] = size[v] + max{ dp[u] | 存在边 u→v 且 u 已处理 }

按拓扑序计算即可。

3. 定向的贪心准则

对于跨边 $(x, y)$：

• 如果 x 和 y 已在同一SCC，方向任意
• 否则，选择使更多SCC合并的方向
• 需要检测方向合法性（不引入环）

4. 环检测优化

使用DSU维护SCC时，可以同时维护SCC之间的偏序关系，快速检测某方向是否会成环。

---

复杂度分析

• SCC计算：$O(n + m)$
• 并查集操作：$O(m \alpha(n))$
• 拓扑排序DP：$O(n + m)$ 总复杂度：$O(n + m)$，适合 $2 \times 10^5$ 的数据规模。

---

理论下界分析

设最终图中SCC缩点后的DAG有 $k$ 个节点，则根据Dilworth定理的推广，最长链点权和至少为 $\lceil \frac{n}{w} \rceil$，其中 $w$ 是DAG的宽度。

但本题中DAG有特殊结构（源于两条链），实际下界通常为 $\max(a, b)$ 或略大，具体取决于跨边的连接模式。

---

总结

本题是一个有向图定向优化问题，核心是将组合优化目标转化为图论标准问题，通过：

1. 问题转化：理解权值与DAG最长链的等价性
2. 结构分析：利用初始图的有向链特性
3. 贪心合并：通过跨边定向最大化SCC合并
4. 高效算法：综合运用SCC、DSU、拓扑DP等技术