题解

CCF 出卡常题，你赢了。

---

题意解析：给定一个 $n+k$ 个点，$m+nk$ 条的图，其中编号从 $n+1$ 至 $n+k$ 的点的度均为 $n$ ，且都分别有一条边连向编号为 $1,2,...,n$ 的点。

连接第 $i$ 条边需要 $W_i$ 个金币；如果你连的边经过了第 $n+i$ 个点，则需额外支付 $C_i$ 金币。

求连接编号为 $1,2,...,n$ 的点的最少金币花费数。

---

注意到 $k$ 很小，考虑枚举选哪些点，然后跑 MST。

时间复杂度 $O(2^km\log m)$，考虑优化。

定义一个图 $G$ 的“全边子图”$G'$ 如下：

• 假设 $G'$ 的点集为 $\{A_1,A_2,...\}$。
• $G'$ 包含且仅包含 $G$ 中所有两边为 $A_i,A_j$ 的边。

结论：对于一个图 $G$ 和它的全边子图 $G'$，它的 MST 的边被全边子图 MST 的边与其它不在全边子图内的边包含。

这个结论很显然，模拟 Kruskal 过程即可。

这样我们可以先对前 $n$ 个点的全边子图求 MST，然后枚举每一条边即可。

时间复杂度 $O(m\log m+2^knk\alpha(n))$，可以得 80pts。

考虑继续运用这个结论。我们可以状压 DP，对于每个状态根据缺任意一个点的状态的 MST 与这个点连的 $n$ 条边得来。这样每次求 MST 的边就降到不超过 $2n+k$ 了。

注意，不能直接 sort，需要 $O(n)$ 归并有序数组。

时间复杂度 $O(m\log m+nk\log n+2^kn\alpha(n))$。

namespace cjdst{
    
    /*class dsu{...};*/
    
    struct edge{
		int x, y, z;
	};
	
	bool cmp(edge *a, edge *b){
		return a -> z < b -> z;
	}
	
	std::vector <edge*> kruskal(int n, std::vector <edge*> a){
		dsu u(n);
		std::vector <edge*> ans;
		for(auto i:a){
			if(u.merge(i -> x, i -> y)) ans.push_back(i);
		}
		return ans;
	}
	
	ll get_len(std::vector <edge*> a){
		ll ans = 0;
		for(auto i:a) ans += i -> z;
		return ans;
	}

	void solve(){
		int n, m, k;
		std::cin >> n >> m >> k;
		std::vector <edge> a(m + k * n + 5);
		std::vector <int> c(k + 5);
		std::vector <std::vector <edge*>> b(k + 5);
		std::vector <edge*> mst;
		for(int i = 1; i <= m; i++){
			std::cin >> a[i].x >> a[i].y >> a[i].z;
			mst.push_back(&a[i]);
		}
		std::sort(mst.begin(), mst.end(), cmp);
		for(int i = 0; i < k; i++){
			std::cin >> c[i];
			for(int j = 1; j <= n; j++){
				int idx = m + i * n + j;
				std::cin >> a[idx].z;
				a[idx].x = n + i + 1, a[idx].y = j;
				b[i].push_back(&a[idx]);
			}
			std::sort(b[i].begin(), b[i].end(), cmp); 
		}
		std::vector <std::vector <edge*>> dp(1 << k);
		dp[0] = kruskal(n, mst);
		ll ans = get_len(dp[0]);
		for(int i = 1; i < (1 << k); i++){
			int j = std::__lg(i & (-i));
			std::vector <edge*> cur(dp[i ^ (1 << j)].size() + b[j].size());
			std::merge(dp[i ^ (1 << j)].begin(), dp[i ^ (1 << j)].end(), b[j].begin(), b[j].end(), cur.begin(), cmp);
			dp[i] = kruskal(n + k, cur);
			ll tmp = get_len(dp[i]);
			for(int j = 0; j < k; j++){
				if(i >> j & 1) tmp += c[j];
			}
			ans = std::min(ans, tmp);
		}
		std::cout << ans << '\n'; 
	}
}