题解：UVA1151 买还是建 Buy or Build
_DATA_X_
·
·
题解
UVA1151 题解：
话说这题真的有紫吗。。。
主要思路：
必备算法：Kruskal 算法、并查集。
不了解 Kruskal 算法的点这里。
先对整个图跑一遍最小生成树，把能用的边存起来，再用一个二进制数记录是否选用当前子网，用并查集进行合并，最后求最小值并输出结果。（具体见代码）
代码实现：
Part1 Kruskal：
直接套模板就可以。
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) ：通过位运算访问二进制数中的每一个值。
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 求最终结果：
```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;
}
``````
~求过。~