1 条题解

  • 0
    @ 2023-9-20 10:33:55

    image

    #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
    上传者