Connect

  你们敢信我看完题解后一边打对？？真的连调都没调，虽然后来证明\(TLE\)了。

  数据范围蛮小的，所以可以用邻接矩阵存边，这样方便查询边权，

  这题是状压\(DP\)。

  从1到\(n\)只有一条路径，那么就是一条链。

  其他的联通块最多只能与链上的的点有一条连边，多了会成环，造成不只一条路径。

  记c[i][s]为当前链延伸到\(i\)为端点，已经考虑过的点的集合为\(s\)的最小花费。

  其中\(s\)不仅包含链上的点，也包含与链通过边相连的联通块中的点。

  转移分为两个方面：

1:向端点连一个点作为新的端点他的代价是山删去所有除了(u,v)以外所有边，u为当前的端点，v为要加入的点。 为什么是所有呢，其实不会有关系，因为其他与v相连的不在链上的的点会在将他的联通块加入时将与他相连的的边的权重新加回来。 2:在链端加入一个联通块，代价是删去所有除了不与u相连的边。

  详细方程见代码。

  虽然一个联通块可能被加在链的多个位置，但考虑当前\(DP\)的端点有可能之后不是端点，那么只考虑向当前端点加入联通块就可以遍历所有状态。

  最后，虽然可以用邻接矩阵，但是复杂度会高，本机跑了一秒多（大数据）。

  后来用前向星优化枚举，本机卡进了一秒。

  然而他在\(OJ\)上\(T\)了，是OJ太垃还是本机不可信？？。

  后来想到了\(lowbit\)这个东西，本以为不会优化太多，结果从0.9直接优化到了0.32。

  真香。。。。。。

Code