https://oj.luyencode.net/problem/ROADS

[utterances-bot]

Khôi phục nông trại - Luyện Code Online

https://oj.luyencode.net/problem/ROADS

[tiend4568]

ac ai cần

include<bits/stdc++.h>

define int long long

using namespace std; int n,m; struct Edge { int u,v; double w; }; Edge e[1000001]; int father [1001]; int sz [1000001]; int check[1001][1001]; int sz_e=0; int x[10001]; int y[10001]; int cmp(Edge a,Edge b) { return a.w<b.w; } int Find(int u) { if (father[u]==u) return u; return father[u]=Find(father[u]); } void Union(int a,int b) { if(sz[a]<sz[b])swap(a,b); father[b]=a; sz[a]+=sz[b]; } void kruskal() { vector mst; double ans=0; int cnt=0; for(int i=1;i<=sz_e;i++) { int a=Find(e[i].u); int b=Find(e[i].v); if(a!=b) { mst.push_back(e[i]); Union(a,b); if(e[i].w>0)ans+=e[i].w; cnt++; if(cnt==n-1)break; } } cout<<setprecision(2)<<fixed<<ans; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++) { father[i]=i; sz[i]=1; } for(int i=1;i<=n;i++)cin>>x[i]>>y[i]; memset(check,0,sizeof(check)); for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; check[u][v]=check[v][u]=1; } for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { sz_e++; Edge k; k.u=i; k.v=j; if(check[i][j]==1)k.w=-1; else k.w=sqrt((x[i]-x[j])(x[i]-x[j])+(y[i]-y[j])(y[i]-y[j])); e[sz_e]=k; }

sort(e+1,e+sz_e+1,cmp);
//for(int i=1;i<=n;i++)cout<<"("<<e[i].u<<","<<e[i].v<<")="<<e[i].w<<endl;
kruskal();

} //code by thần đồng k12