Pagini recente » Cod sursa (job #1309364) | Cod sursa (job #483595) | Cod sursa (job #447916) | Cod sursa (job #3344044) | Cod sursa (job #3344045)
#include <bits/stdc++.h>
using namespace std;
ifstream f("desen.in");
ofstream g("desen.out");
int t,n,m,i,j,a,b,c,d;
vector<pair<int,int>>adj;
double ans,dist;
int fat[2003],sz[2003];
void make_set(int node){
fat[node]=node;
sz[node]=1;
}
int get_fat(int node){
if (fat[node]==node)return node;
return fat[node]=get_fat(fat[node]);
}
void unite_set(int a,int b){
a=get_fat(a);
b=get_fat(b);
if (sz[a]>sz[b])swap(a,b);
if (a!=b){
fat[a]=b;
sz[b]+=a;
}
}
priority_queue<tuple<double,int,int>,
vector<tuple<double,int,int>>,greater<tuple<double,int,int>>>GL;
int main()
{ f>>t;
while(t--){
f>>a>>b;
adj.push_back({a,b});
priority_queue<tuple<double,int,int>,
vector<tuple<double,int,int>>,greater<tuple<double,int,int>>>PQ;
for (i=0;i<adj.size()-1;i++){
tie(c,d)=adj[i];
double dist=sqrt((a-c)*(a-c)+(b-d)*(b-d));
GL.push({dist,i,adj.size()-1});
}
PQ=GL;
ans=0;
while(GL.size())GL.pop();
for (i=0;i<adj.size();i++){
make_set(i);
}
while(!PQ.empty()){
tie(dist,a,b)=PQ.top();
PQ.pop();
if (get_fat(a)!=get_fat(b)){
unite_set(a,b);
ans+=dist;
GL.push({dist,a,b});
}
}
g<<fixed<<setprecision(7)<<ans<<'\n';
}
return 0;
}