﻿ 题解 UVA1151Buy or Build （最小生成树）

### 代码

``````#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010, maxm = 1e6 + 10;
int n,fa[maxn],ans,sum,q,x[maxn],y[maxn],w[maxn][maxn],num,c[maxn],_cnt;
struct Edge{
int from,to,val;
}e[maxm];
Edge r[maxn]; //要用的边

bool cmp(Edge x, Edge y){return x.val < y.val;}

int get(int x){return fa[x] == x ? x : fa[x] = get(fa[x]);}

void Kruskal0(){
int cnt = 0;
sort(e + 1, e + 1 + num, cmp);
for(int i = 1; i <= num; ++ i){
int u = e[i].from, v = e[i].to;
int q1 = get(u), q2 = get(v);
if(q1 != q2){
fa[q1] = q2; cnt ++;
r[cnt] = e[i]; ans += e[i].val;  //保留要用的边
}
if(cnt >= n - 1) break;
}
num = cnt;
}

void Kruskal(){
for(int i = 1; i <= num; ++ i){
int q1 = get(r[i].from), q2 = get(r[i].to);
if(q1 != q2){
fa[q1] = q2; _cnt ++;
sum += r[i].val;
}
if(_cnt >= n - 1) break;
}
}

void get_ans(){
for(int ss = 0; ss < (1 << q); ++ ss){  //状压枚举
sum = 0; _cnt = 0;
for(int i = 1; i <= n; ++ i) fa[i] = i;
for(int k = 1; k <= q; ++ k)
if(ss & (1 << k - 1)){
sum += c[k];
for(int i = 1; i < w[k][0]; ++ i)
for(int j = i + 1; j <= w[k][0]; ++ j){
int q1 = get(w[k][i]), q2 = get(w[k][j]);
if(q1 != q2) fa[q1] = q2, _cnt ++;
}
}
Kruskal();
ans = min(ans, sum);
}
}

int main(){
int T;
scanf("%d", &T);
while(T--){
sum = ans = num = 0;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++ i) fa[i] = i;
for(int i = 1; i <= q; ++ i){
scanf("%d%d", &w[i][0], &c[i]);
for(int j = 1; j <= w[i][0]; ++ j) scanf("%d", &w[i][j]);
}
for(int i = 1; i <= n; ++ i) scanf("%d%d", &x[i], &y[i]);
for(int i = 1; i < n; ++ i)
for(int j = i + 1; j <= n; ++ j){
int dis = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
e[++num].from = i, e[num].to = j, e[num].val = dis;
}
Kruskal0();
get_ans();
printf("%d
", ans);
if(T) cout << endl;   //UVA的神仙格式
}
return 0;
}
``````