当 $n=1$ 时答案为 $0$，$n=2$ 时无解。

$n\ge 3$ 时显然有解。先缩 SCC，缩完一定是一条链。然后求出第 $i$ 个（按拓扑序编号）SCC 到第 $j\pod{i< j}$ 个 SCC 的权值最小的边。则问题可以转化为选择若干条边覆盖了 $[1,m)$（$m$ 是 SCC 个数）这整个区间。这个问题可以用简单的 DP 解决，同时构造方案。时间复杂度 $O(n^2)$。

正确性的证明： 我们每次找到一条边 $u\to v$ 满足以下条件之一，那么翻转后 $u,u+1,\ldots,v$ 这些点都在同一个 SCC 内。条件：

• $u$ 或 $v$ 的大小（即 SCC 内的点数）大于 $1$。
• $u+1< v$，即 $u$, $v$ 不相邻。

显然当 $m< n $ 或第二个条件满足时，总是存在一个选择边的顺序，因此最后图一定是强连通的。唯一的特例是 $n=m$ 且我们翻转了 $1\to 2,2\to 3,\ldots,n-1\to n$ 这些边，由于 $n\ge 3$，容易验证这是合法的。