题解：UVA1151 买还是建 Buy or Build

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int T,n,q,f[N];//分别表示样例组数，节点个数，网络数，并查集用的父亲数组。 
int X[N],Y[N],w[N];//分别表示各个节点的横坐标，纵坐标，以及各个网络的价格。 
int in[10][N];//存储网络联通的各个节点编号 
struct node{
	int x,y,z;
	bool operator<(node A)const{
		return z<A.z;
	}
};
vector<node>edge;
inline int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
	cin>>T;
	while (T--){
		edge.clear();
		cin>>n>>q;
		for (int i=1;i<=q;i++){
			cin>>in[i][0]>>w[i];
			for (int j=1;j<=in[i][0];j++)
				cin>>in[i][j];
		}
		for (int i=1;i<=n;i++){
			cin>>X[i]>>Y[i];
			for (int j=1;j<i;j++){
				edge.push_back({i,j,
				(X[i]-X[j])*(X[i]-X[j])+
				(Y[i]-Y[j])*(Y[i]-Y[j])});
			}
		}sort(edge.begin(),edge.end());
		int res=0,ans=0;
		for (int i=1;i<=n;i++)f[i]=i;
		for (int i=0;i<edge.size();i++){
			int x=edge[i].x,y=edge[i].y;
			x=find(x);y=find(y);
			if (x!=y){
				edge[res++]=edge[i];
				f[x]=y;
				ans+=edge[i].z;
			}
		}
		int s=(1<<q)-1;
		for (int i=1;i<=s;i++){
			int cnt=0;
			for (int j=1;j<=n;j++) f[j]=j;
			for (int j=1;j<=8;j++)
				if (i&(1<<j-1)){
					cnt+=w[j];
					for (int k=2;k<=in[j][0];k++){
						int x=in[j][k];
						int y=in[j][k-1];
						x=find(x);
						y=find(y);
						if (x!=y) f[x]=y;
					}
				}
			for (int j=0;j<n;j++){
				int x=edge[j].x,y=edge[j].y;
				x=find(x);y=find(y);
				if (x!=y){
					f[x]=y;
					cnt+=edge[j].z;
				}
			}
			ans=min(ans,cnt);
		}cout<<ans<<'\n';
		if (T) cout<<'\n';
	}
	return 0;
}