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;
}
0 条评论