hdu1875
1718 ワード
/*
: ,
*/
#include
#include
#include
#include
#include
#include
using namespace std;
struct edge
{
int from,to;
double w;
};
struct di
{
int x,y;
};
int pre[101];
di a[101];
vectoredges;
int n,m;
bool comp( edge a, edge b){
return a.w < b.w; //
}
void addedge(int x,int y,double w)
{
edge v={x,y,w};
edges.push_back(v);
}
int find(int x)
{
if(x==pre[x])
{
return x;
}
else
{
pre[x]=find(pre[x]);
return pre[x];
}
}
void kluska()
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
}
double sum;
int top=n;
for(int i=0;i1000) continue;//
int f1=find(v.from);
int f2=find(v.to);
if(f1!=f2)
{
pre[f2]=f1;
top--;
sum+=v.w;
}
}
if(top==1) printf("%.1lf
",sum*100);
else printf("oh!
");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
edges.clear();
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
double sum=sqrt((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y));
addedge(i,j,sum);
}
}
sort(edges.begin(),edges.end(),comp);
kluska();
}
}