UVA1151题解

SP_beyond_xxxx · 2025-07-10 14:45:08 · 题解

思路

看到 1\le q\le8 我直接就想到了状压暴力枚举，先建最小生成树，用 Kruskal 算法，然后连边分别计算买和建，在计算最小值即可。
注意输出的空白行。

代码

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