UVA1151 题解：

~~话说这题真的有紫吗。。。~~

主要思路：

必备算法：

Kruskal

算法、并查集。

不了解

Kruskal

算法的点这里。

先对整个图跑一遍最小生成树，把能用的边存起来，再用一个二进制数记录是否选用当前子网，用并查集进行合并，最后求最小值并输出结果。（具体见代码）

代码实现：

Part1 Kruskal：

直接套模板就可以。

CPP

	sort(e+1,e+m+1,cmp);
	int res=0,ans=0;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y;
		x=find(x),y=find(y);
		if(x!=y){
			e[++res]=e[i];//状态压缩
			fa[x]=y;
			ans+=e[i].z;
		}
	}

Part2 二进制数记录是否选用子网：

部分代码解释：

i&(1<<j-1) ：通过位运算访问二进制数中的每一个值。

CPP

	int s=(1<<q)-1;
	for(int i=1;i<=s;i++){
		int ans2=0;
		for(int j=1;j<=n;j++){
			fa[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];int y=in[j][k-1];
					x=find(x);y=find(y);
					if(x!=y){
						fa[x]=y;
					}
				}
			}
		}

Part3 求最终结果：

ans

指最小生成树的结果，

ans2

指如选用当前子网后的结果。

CPP

		for(int j=1;j<=n;j++){
			int x=e[j].x,y=e[j].y;
			x=find(x),y=find(y);
			if(x!=y){
				fa[x]=y;
				ans2+=e[j].z;
			}			
		}
		ans=min(ans,ans2);
	}

Part4 AC Code：

vjudge 上AC了，应该是标程。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{c=getchar();if(c=='-')sign=-1;}while(!isdigit(c));
	do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
	x*=sign;
}
int n,q;
int in[9][N],w[9],fa[N],X[N],Y[N];
struct edge{
	int x,y,z;
}e[N*N];
const bool cmp(edge x,edge y){
	return x.z<y.z;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve(){
	read(n);read(q);
	for(int i=1;i<=q;i++){
		read(in[i][0]);
		read(w[i]);
		for(int j=1;j<=in[i][0];j++){
			read(in[i][j]);
		}
	}
	int m=0;
	for(int i=1;i<=n;i++){
		read(X[i]);read(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+m+1,cmp);
	int res=0,ans=0;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y;
		x=find(x),y=find(y);
		if(x!=y){
			e[++res]=e[i];
			fa[x]=y;
			ans+=e[i].z;
		}
	}
	int s=(1<<q)-1;
	for(int i=1;i<=s;i++){
		int ans2=0;
		for(int j=1;j<=n;j++){
			fa[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];int y=in[j][k-1];
					x=find(x);y=find(y);
					if(x!=y){
						fa[x]=y;
					}
				}
			}
		}
		for(int j=1;j<=n;j++){
			int x=e[j].x,y=e[j].y;
			x=find(x),y=find(y);
			if(x!=y){
				fa[x]=y;
				ans2+=e[j].z;
			}			
		}
		ans=min(ans,ans2);
	}
	cout<<ans<<endl;
}
signed main(){
	int t;
	read(t);
	while(t--){
		solve();
		if(t){
			cout<<endl;//注意格式！！！（被卡了好多次）
		}
	}
	return 0;
}

~求过。~

题解：UVA1151 买还是建 Buy or Build

文章操作