PKU 2560-Freckles

問題概要

N個の点が与えられる。点間に直線を引いて全ての点同士で移動が可能にする時に最小の線の長さの合計を求めよ。

解法

最小全域木

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
struct Edge{
        int src,dst;double cost;
};
Edge Edges[500*500];
int m;
int n;
int T;
bool operator<(const Edge &a,const Edge &b){
        return a.cost<b.cost;
}
struct UnionFind{
        vector<int> par;
        UnionFind(int n){
                par=vector<int>(n);
                for(int i=0;i<n;i++)par[i]=i;
        }
        int find(int x){
                if(par[x]==x)return x;
                return par[x]=find(par[x]);
        }
        void unite(int x,int y){
                x=find(x);y=find(y);
                if(x==y)return;
                par[x]=y;
        }
        bool same(int x,int y){
                return find(x)==find(y);
        }
};

int main(){
        T=1;
        while(T--){
                m=0;
                scanf("%d",&n);
                double x[n],y[n];
                for(int i=0;i<n;i++)scanf("%lf%lf",x+i,y+i);
                for(int i=0;i<n;i++){
                        for(int j=0;j<n;j++){
                                Edges[m++]=(Edge){i,j,hypot(x[i]-x[j],y[i]-y[j])};
                        }
                }
                stable_sort(Edges,Edges+m);
                UnionFind uf(n);
                double ans=0;
                for(int i=0;i<m;i++){
                        if(uf.same(Edges[i].src,Edges[i].dst))continue;
                        ans+=Edges[i].cost;
                        uf.unite(Edges[i].src,Edges[i].dst);
                }
                printf("%.2f\n",ans);
        }
}