CCF 出卡常题，你赢了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意解析：给定一个 n+kn+kn+k 个点，m+nkm+nkm+nk 条的图，其中编号从 n+1n+1n+1 至 n+kn+kn+k 的点的度均为 nnn ，且都分别有一条边连向编号为 1,2,...,n1,2,...,n1,2,...,n 的点。
连接第 iii 条边需要 WiW_iWi 个金币；如果你连的边经过了第 n+in+in+i 个点，则需额外支付 CiC_iCi 金币。
求连接编号为 1,2,...,n1,2,...,n1,2,...,n 的点的最少金币花费数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意到 kkk 很小，考虑枚举选哪些点，然后跑 MST。
时间复杂度 O(2kmlogm)O(2^km\log m)O(2kmlogm)，考虑优化。
定义一个图 GGG 的“全边子图”G′G'G′ 如下：
* 假设 G′G'G′ 的点集为 {A1,A2,...}\{A_1,A_2,...\}{A1 ,A2 ,...}。
* G′G'G′ 包含且仅包含 GGG 中所有两边为 Ai,AjA_i,A_jAi ,Aj 的边。
结论：对于一个图 GGG 和它的全边子图 G′G'G′，它的 MST 的边被全边子图 MST 的边与其它不在全边子图内的边包含。
这个结论很显然，模拟 Kruskal 过程即可。
这样我们可以先对前 nnn 个点的全边子图求 MST，然后枚举每一条边即可。
时间复杂度 O(mlogm+2knkα(n))O(m\log m+2^knk\alpha(n))O(mlogm+2knkα(n))，可以得 80pts。
考虑继续运用这个结论。我们可以状压 DP，对于每个状态根据缺任意一个点的状态的 MST 与这个点连的 nnn 条边得来。这样每次求 MST 的边就降到不超过 2n+k2n+k2n+k 了。
注意，不能直接 sort，需要 O(n)O(n)O(n) 归并有序数组。
时间复杂度 O(mlogm+nklogn+2knα(n))O(m\log m+nk\log n+2^kn\alpha(n))O(mlogm+nklogn+2knα(n))。
