SOLUTION FROM WUMIN4
题意
给出一个 \(n\) 个点的带权竞赛图（定向完全图），你可以进行任意次操作，每次操作反转一条边，代价为边权，求使得图强连通的最小代价和与方案，或输出无解。
\(n\le 2000\)。
思路
我们先考虑算出这张图的所有 SCC 并进行缩点，容易发现缩点后图是一个 DAG，且每个 SCC 中的边都没有必要翻转（翻转后显然不会更优）。于是问题变为了翻转 DAG 上边的最小代价使得图强连通。
注意竞赛图有一个很重要的性质：竞赛图缩点后拓扑序成链状，拓扑序小的点向所有拓扑序比它大的点连边。
于是我们可以对 DAG 建立一个图，正向边边权为 \(0\)，反向边为原图边权，接着从原图拓补序最小的点跑最短路，到拓补序最大的点即为答案，然后求一下方案即可。