Buy or Build UVA - 1151 买还是建 最小生成树+二进制枚举子集

题目链接 

平面上有n个点（1≤n≤1000），你的任务是让所有n个点连通。为此，你可以新建一些边，费用等于两个端点的欧几里德距离。另外还有q（0≤q≤8）个“套餐”可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通。第i个套餐的花费为Ci。如图11-6所示，一共有3个套餐：

它的最优解是购买套餐1和套餐2，然后手动连接两条边，如图11-7所示。 

【分析】
    最容易想到的算法是：先枚举购买哪些套餐，把套餐中包含的边的权值设为0，然后求最小生成树。由于枚举量为O(2q)，给边排序的时间复杂度为O(n2logn)，而排序之后每次Kruskal算法的时间复杂度为O(n2)，因此总时间复杂度为O(2qn2+n2logn)，对于题目的规模来说太大了。
    只需一个小小的优化即可降低时间复杂度：先求一次原图（不购买任何套餐）的最小生成树，得到n-1条边，然后每次枚举完套餐后只考虑套餐中的边和这n-1条边，则枚举套餐之后再求最小生成树时，图上的边已经寥寥无几。
    为什么可以这样呢？首先回顾一下，在Kruskal算法中，哪些边不会进入最小生成树。答案是：两端已经属于同一个连通分量的边。买了套餐以后，相当于一些边的权变为0，而对于不在套餐中的每条边e，排序在e之前的边一个都没少，反而可能多了一些权值为0的边，所以在原图Kruskal时被“扔掉”的边，在后面的Kruskal中也一样会被扔掉。
    本题还有一个地方需要说明：因为Kruskal在连通分量包含n个点时会终止，所以对于随机数据，即使用原始的“暴力算法”，也能很快出解。如果你是命题者，可以这样出一个数据：有一个点很远，而其他n-1个点相互比较近。这样，相距较近的n-1个点之间的C(n-1,2)条边会排序在前面，每次Kruskal都会先考虑完所有这些边。而考虑这些边时是无法让远点和近点连通的。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000+5 , Q = 8; 
int x[N], y[N], cost[Q];
vector<int> sub[Q];
int n, q, f[N];
struct Edge{
	int u, v, w;
	Edge(int a,int b,int c) : u(a), v(b), w(c) { };
	bool operator < (Edge a){
		return w < a.w;
	}
};
 
int find(int x){
	return x == f[x] ? x : f[x] = find(f[x]);
}
// cnt是当前组件的数量
int MST(int cnt,const vector<Edge> &e, vector<Edge> &used){
	if(cnt == 1) return 0; 
	int ans = 0;
	used.clear();
	for(int i = 0; i < e.size(); i++){
		int a = find(e[i].u), b = find(e[i].v);
		if(a != b){
			f[a] = b;
			ans += e[i].w;
			used.push_back(e[i]);
			if( --cnt == 1) break;
		}
	}
	return ans;
}
 
 
 
int main(int argc, char *argv[]) {	
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i = 0; i < q; i++){
			int cnt;
			scanf("%d%d",&cnt,&cost[i]);
			sub[i].clear();
			while(cnt--){
				int u;
				scanf("%d",&u);
				sub[i].push_back(u-1);
			}
		}
		for(int i = 0; i < n; i++)  scanf("%d%d",&x[i],&y[i]);
		
		vector<Edge> e, need;
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				int w = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
				e.push_back( Edge(i,j,w));
			}
		}
		for(int i = 0; i < n; i++) f[i] = i;
		sort( e.begin(), e.end());
		
		int ans = MST(n,e,need); 
		for(int mask = 1; mask < (1 << q); mask++){ //二进制枚举子集
			//连接在同一网络集的城市。 
			for(int i = 0; i < n; i++) f[i] = i;
			int cnt = n, c = 0;
			for(int i = 0; i < q; i++){
				if( mask & (1 << i)){ 
					c += cost[i];
					for(int j = 1; j < sub[i].size(); j++){
						int u = find(sub[i][j]), v = find(sub[i][0]);
						if( u != v){
							f[u] = v;
							cnt--;  
						}
					}
				}
			} 
			vector<Edge> dummy;
      		ans = min(ans, c + MST(cnt, need, dummy));
		}
		printf("%d\n",ans);
		if(T) printf("\n");
	}
	return 0;
}