UVA1151题解

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+50;
int n,q;//n： 城市的总数，q： 子网数量 
int in[9][N],w[9],p[N],X[N],Y[N];//in[i][0]： 城市的数量，w[i]：子网费用，in[i][1~in[i][0]]：城市
//X[i]，Y[i]城市坐标 
//p[i]：熟悉的并查集 
struct edge{
	int x,y,z;//坐标  费用 
}e[N*N];
const bool cmp(edge a,edge b){
	return a.z<b.z;
}//按距离排序 
inline int get_p(int x){
	return p[x]==x?x:p[x]=get_p(p[x]);//路径压缩 
} //Find
inline void solve(){
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>in[i][0];
		cin>>w[i];
		for(int j=1;j<=in[i][0];++j){
			cin>>in[i][j];
		}
	}//UVA特有读入 
	
	//开始 build 
	
	int m=0;
	for(int i=1;i<=n;i++)
	{
		cin>>X[i]>>Y[i]; 
		for(int j=1;j<i;j++){
			e[++m].x=i;
			e[m].y=j;
			e[m].z=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
			//记录平面每个点坐标，费用 
		} 
	}
	sort(e+1,e+1+m,cmp);//排序 
	int res=0,ans=0;
	for(int i=1;i<=n;i++)p[i]=i;//初始化并查集 
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y;
		x=get_p(e[i].x),y=get_p(e[i].y);
		if(x!=y){
			e[++res]=e[i];//记录边 
			p[x]=y;
			ans+=e[i].z; //更新最少费用 
		}//合并 
	}
	
	// 开始 buy 
	
	int s=(1<<q)-1;// 0/1 二进制表示判断选 or 不选 
	for(int i=1;i<=s;i++){
		int ans2=0;
		for(int j=1;j<=n;j++)p[j]=j;//初始化 
		for(int j=1;j<=8;j++){
			if(i&(1<<j-1)){
				ans2+=w[j];//买子网 
				for(int k=2;k<=in[j][0];k++){
					int x=in[j][k],y=in[j][k-1];
					x=get_p(x);y=get_p(y);
					if(x!=y)p[x]=y;//并城市 
				}
			}
			
		}for(int j=1;j<n;j++){
				int x=e[j].x,y=e[j].y;
				x=get_p(e[j].x),y=get_p(e[j].y);
				if(x!=y){
					p[x]=y;
					ans2+=e[j].z; //计算费用 
				}
			}
		ans=min(ans,ans2);//计算最小值 
	}
	cout<<ans<<endl;//输出 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;//读入 
	while(T--){
		solve();
		if(T)cout<<endl;//一定要空行隔开！！！ 
	}
	return 0;
}