思路： n , m n,m n,m等价，可假设 n ≤ m n\le m n≤m
分情况讨论：
1. n = = m 1.n==m 1.n==m
a n s = 2 ( A n n ) 2 ans=2(A_n^n)^2 ans=2(Ann)2
2. n = m − 1 n=m-1 n=m−1
a n s = A n n × A m m ans=A_{n}^{n}\times A_{m}^m ans=Ann×Amm
3. n < m n<m n<m
a n s = 0 ans=0 ans=0
思路：最小生成树。
显然直接暴力加所有边。
考虑对按 x x x排序后。
若三个点 A , B , C A,B,C A,B,C
A , B A,B A,B连边 x b − x a x_b-x_a xb−xa， B , C B,C B,C连边 x c − x b x_c-x_b xc−xb
则 A , C A,C A,C不用再连边 x c − x a x_c-x_a xc−xa
同理：不用连 y c − y a y_c-y_a yc−ya
综上只用连相邻的 x b − x a , y b − y a x_b-x_a,y_b-y_a xb−xa,yb−ya
然后对这 2 ( n − 1 ) 2(n-1) 2(n−1)条边进行排序， k r u s k a l kruskal kruskal即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int r[N]; struct edge{ int u,v,w; bool operator<(const edge& e)const{ return w<e.w; } }e[N<<1]; struct point{ int x,y,id; }a[N]; bool cmp1(point a,point b){ return a.x<b.x; } bool cmp2(point a,point b){ return a.y<b.y; } int find(int x){ return r[x]==x?x:r[x]=find(r[x]); } int main(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; a[i].id=r[i]=i; } sort(a+1,a+n+1,cmp1); int s=0; for(int i=2;i<=n;i++){ e[s++]={a[i-1].id,a[i].id,a[i].x-a[i-1].x}; } sort(a+1,a+n+1,cmp2); for(int i=2;i<=n;i++){ e[s++]={a[i-1].id,a[i].id,a[i].y-a[i-1].y}; } sort(e,e+s); int tot=0; ll ans=0; for(int i=0;i<s;i++){ int u=e[i].u,v=e[i].v; u=find(u),v=find(v); if(u!=v){ r[u]=v; tot++; ans+=e[i].w; } if(tot==n-1) break; } cout<<ans<<endl; return 0; }