2022/08/09 做题记录

Posted on 2022-08-09 Disqus:

一个点集为原图，边集极小的强连通图一定可以从一个只包含一个点的强连通分量，每次加一条两端在当前强连通分量里，而中间不在的链或环扩展而成（容易发现这样加入后仍然是强连通分量）。

证明：每次当前强连通分量的点集和剩下的点集之间一定存在一个环（否则就不强连通了），可以通过添加这个环（或它的一部分）继续扩展。

而这和原问题的关系是：我们可以将一条边边权较小的一个方向的权值赋为0，较大的一个方向赋为它们的差，这样这个边集极小的强连通图的最小边权和加上所有边边权较小的那一个方向的权值就是答案。

于是我们设 f[S] 代表组成一个点集为 S 的强连通分量的最小代价，g[S][x][y] 表示当前的点集合为 S，我们还需要加入一条从 x 到 y 的链的最小代价。

g 向 f 转移是直接加上 x-->y 这条边使这个链/环闭合。

f 向 g 转移是如果下一个加入的是链，枚举起点和终点是什么，如果是环枚举起点，第一条边和第二条边（因为不能加重边）。

g 向 g 转移是枚举下一个点是什么。

时间复杂度 $O(n \log^3 n)$

代码: http://47.92.197.167:5283/submission/107346

赛时想到的是记录 f[x][S] 代表确定了一棵以 x 为根的 dfs 树子树，包含的点有 S, 这样方便转移（因为不可能有横叉边），但是 $O(3^n)$ ，根本想不到怎么优化。

感觉有能在想出一个看起来很对，但完全没有前途的想法时重新思考的能力很不容易。。。