1 条题解
-
0
#include <bits/stdc++.h> #define ll long long #define mid (l+r>>1) using namespace std; const int N=105; int n,m,k,s,t,pre[11],fa[N],tot; struct node{ int x,y; bool operator<(const node &k)const{ return x<k.x; } }a[N]; struct node1{ int x,y; ll l; bool operator<(const node1 &k)const{ return l<k.l; } }e[N*11]; ll ans; ll calc(int i,int j){ return (ll)(a[i].x-a[j].x)*(a[i].x-a[j].x)+(ll)(a[i].y-a[j].y)*(a[i].y-a[j].y); } int getfa(int u){ return fa[u]==u?u:fa[u]=getfa(fa[u]); } int main(){ cin>>n; for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y; sort(a+1,a+1+n); for (int i=1;i<=n;++i){ for (int j=0;j<=10;++j) if (pre[j]) e[++tot]={pre[j],i,calc(pre[j],i)}; pre[a[i].y]=i; } sort(e+1,e+1+tot); for (int i=1;i<=n;++i) fa[i]=i; for (int i=1;i<=tot;++i){ s=getfa(e[i].x); t=getfa(e[i].y); if (s!=t) ans+=e[i].l,fa[s]=t; } cout<<ans; }
- 1
信息
- ID
- 506
- 时间
- 4000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 32
- 已通过
- 11
- 上传者