/* 给出n个点，要求距离小于10或大于1000不能建边，问联通这些点至少需要的距离 不存在输出-1 */ #include<cstdio> #include<vector> #include<cmath> #include<algorithm> using namespace std; struct Dot { double x,y; }dot[105]; double caculateDistance(const Dot a,const Dot b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } struct Node { int p,q; double dis; bool friend operator < (Node a,Node b) { return a.dis < b.dis; } }; vector<Node> data; int f[105]; //父节点 int find(int x) { if (x != f[x]) f[x] = find(f[x]); return f[x]; } bool join(int x,int y) { int fx = find(x); int fy = find(y); if (fx != fy) { f[fx] = fy; return true; } return false; } int main() { int n; scanf ("%d",&n); for (int i = 1 ; i <= n ; i++) f[i] = i; for (int i = 1 ; i <= n ; i++) scanf ("%lf%lf",&dot[i].x,&dot[i].y); for (int i = 1 ; i <= n ; i++) { for (int j = i+1 ; j <= n ; j++) { double dis = caculateDistance(dot[i],dot[j]); if (dis >= 10 && dis <= 1000) { Node t; t.p = i; t.q = j; t.dis = dis; data.push_back(t); } } } sort(data.begin(),data.end()); int ant = 0; //已经连上的边 double ans = 0; for (int i = 0 ; i < data.size() ; i++) { if (join(data[i].p,data[i].q)) { ans += data[i].dis; ant++; } if (ant == n-1) //剪枝 break; } if (ant == n-1) printf ("%lf\n",ans); else printf ("-1\n"); return 0; }
