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