题解：UVA1151 买还是建 Buy or Build

· · 题解

看到题目的 q\le8，非常小，可以直接先提前跑一遍最小生成树，跑完后再用 O(2^q) 效率枚举购买的网络，最后取最小值输出即可（记得输出两个换行）。 

#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;
}