POJ 2784 Buy or Build

n个城市，告诉每个城市的坐标，还有q个联通块，现在要把这n个城市连起来，可以购买联通块（每个有一定的费用），或者新建一条边（费用为点之间的距离的平方），问最小费用是多少。

二进制枚举每个联通块的选择情况。

注意联通块的数量大小应该就可以判断出要枚举。然后每次都跑一边最小生成树算出最优的答案。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using std::vector;
struct edge {
    int from,to;double v;
    bool operator < (const edge m) const {
        return v<m.v;
    }
}e[1020*1020];
struct V{
    int x,y;
}v[1020];
std::vector<int> vec[10];
int fa[1200],cost[10],n,m,cnt;
double ans=1e20;
inline int getdis(V a,V b){
    double s=(a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y);
    return s*1.0;
}
inline int add(int a,int b,double cost){
    cnt++;
    e[cnt].from=a,e[cnt].to=b,e[cnt].v=cost;
    return 0;
}
inline int find(int x){
    return fa[x]==0?x:fa[x]=find(fa[x]);
}
inline double mst(int tot,double cost){
    if(tot==n-1){
        ans=std::min(ans,cost);
    }
    for(int i=1;i<=n*n;++i){
        int t1=find(e[i].from),t2=find(e[i].to);
        if(t1==t2) continue;
        fa[t1]=t2;
        cost+=e[i].v;
        tot++;
        if(tot==n-1) break;
    }
    ans=std::min(ans,cost);
    return 1;
}
int main (){
//  freopen("data.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int x;
        scanf("%d %d",&x,&cost[i]);
        for(int j=1;j<=x;++j){
            int y;
            scanf("%d",&y);
            vec[i].push_back(y);
        }
    }
    for(int i=1;i<=n;++i){
        scanf("%d %d",&v[i].x,&v[i].y);
    }
    for(int i=1;i<=n;++i){
        for(int j=1+i;j<=n;++j){
            double s=getdis(v[i],v[j]);
            add(i,j,s);
        }
    }
    std::sort(e+1,e+1+cnt);
    for(int i=0;i<=((1<<m)-1);++i){
        int tot=0;double c=0;
        memset(fa,0,sizeof(fa));
        for(int j=0;j<m;++j){
            int root=0;
            if((i&(1<<j))!=0){
                c+=cost[1+j];
                for(vector<int>::iterator it=vec[j+1].begin();it!=vec[1+j].end();++it){
                    if(!root) root=*it;
                    else {
                        int t1=find(*it),t2=find(root);
                        if(t1==t2) continue;
                        fa[t1]=t2;tot++;
                    }
                }
            }
        }
        mst(tot,c);
    }
    printf("%.0lf",ans);
    return 0;
}