uva 10034

제목 의 대 의 는 평면 에 n 개의 점 이 있 습 니 다.잉크 펜 으로 이 점 들 에 선 을 그 어 모든 점 이 서로 연결 되 고 잉크 를 가장 적 게 사용 해 야 합 니 다.사고방식 은 코드 아래 에 있다.

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<cmath>
#include <iomanip>

using namespace std;
struct point
{
    double x,y;
};
point p[101];
struct edge
{
    int from,to;
    double dist;
};
bool cmp(const edge &a,const edge &b)
{
    return a.dist<b.dist;
}
edge e[10001];
int father[10000];
int rank[10000];
void ini(int n)
{
    for(int i=0;i<n;i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}
int Find(int x)
{
    if(x!=father[x])
    father[x]=Find(father[x]);
    return father[x];
}
bool merge(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    if(a==b)
    return false;
    else
    {
        if(rank[a]>rank[b])
        father[b]=a;
        else
        {
            if(rank[a]==rank[b])
            rank[b]++;
            father[a]=b;
        }
    }
    return true;
}
double dis(point x,point y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
int main()
{
    ios::sync_with_stdio(false);
    int n,k,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        k=0;
        for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                e[k].dist=dis(p[i],p[j]);
                e[k].from=j;
                e[k].to=i;
                k++;
            }
        }
/* for(int i=0;i<k;i++) cout<<e[i].from<<" "<<e[i].to<<" "<<e[i].dist<<endl;*/
        sort(e,e+k,cmp);
        ini(n);
        double ans=0;
        for(int i=0;i<k;i++)
        {
            edge ee=e[i];
            if(merge(ee.from,ee.to))
            ans+=ee.dist;
        }
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
        if(t)
        cout<<endl;
    }
    return 0;
}

아이디어 누 드 의 최소 생 성 트 리 입 출력 형식 에 주의 하면 됩 니 다.