1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; const int maxn=1001; int n,m,f[maxn],tot; bool vis[1001][1001]; struct node { int x,y; }g[maxn]; struct tree { int x,y;double d; }tr[1000007]; double dis(int x1,int y1,int x2,int y2) { return (double)sqrt((double)(x2-x1)*(x2-x1)+(double)(y2-y1)*(y2-y1)); } double ans; bool comp(tree &a,tree &b) { if(a.d==b.d) return a.x<b.x; return a.d<b.d; } int find(int x) { if(f[x]==x) return x; return f[x]=find(f[x]); } void krucal() { for(int i=1;i<=tot;i++) { int x1=tr[i].x,y1=tr[i].y; int a1=find(x1),b1=find(y1); if(a1!=b1) { f[a1]=b1; ans+=tr[i].d; } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) { cin>>g[i].x>>g[i].y; } for(int i=1;i<=m;i++) { int x,y;cin>>x>>y;vis[x][y]=1,vis[y][x]=1; int a=find(x),b=find(y); if(a!=b) f[a]=b; } for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { if(vis[i][j]==0) tr[++tot].x=i,tr[tot].y=j,tr[tot].d=dis(g[i].x,g[i].y,g[j].x,g[j].y); } } sort(tr+1,tr+1+tot,comp); krucal(); printf("%.2lf",ans); return 0; }
|