P2872 [USACO07DEC] Building Roads S

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=1010,M=1000*500+50;
int n,m;
int x[N],y[N];
struct Edge{int a,b;double w;bool operator<(const Edge& W) const{return w<W.w;}
}edges[M];
int p[N];
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}double get_dist(int i,int j)
{double dx=x[i]-x[j],dy=y[i]-y[j];return sqrt(dx * dx + dy * dy);
}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}for(int i=1;i<=m;i++){cin>>edges[i].a>>edges[i].b;}for(int i=1;i<=n;i++) p[i]=i;int cnt=0;for(int i=1;i<=m;i++){int a=find(edges[i].a),b=find(edges[i].b);double w=edges[i].w;if(a!=b){p[a]=b;cnt++;}}int edge_cnt=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){edges[++edge_cnt]={i,j,get_dist(i,j)};}}sort(edges+1, edges+edge_cnt+1);double res=0;for(int i=1;i<=edge_cnt;i++){int a=find(edges[i].a),b=find(edges[i].b);double w=edges[i].w;if(a!=b){p[a]=b;res+=w;if(++cnt==n-1){break;}}}cout<<fixed<<setprecision(2)<<res<<"\n";return 0;}