题意:给出n个点的坐标,连接每两个点之间的的花费是min(|x1-x2|, |y1-y2|)。求将这些点连接起来的最小花费。


题解:要是数据给的小的话,这题就是最小生成树的模板题了,但是这里给出的点的大小是10^5,并且还给出了两个点之间的最小花费是min(|x1-x2|, |y1-y2|),那么可以先将x坐标排序,这样两个点之间的最小距离就是他们相邻两个点的x轴的距离了,我们push一个u->v,花费为|x1-x2|的边到边集里。同样对y轴进行处理,为了处理最小生成树方便,我们反向push一个v->u,花费为|y2-y1|的边到边集,之后就是正常的最小生成树处理即可。


代码:

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const LL mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
int n, fa[maxn], cnt;
 
struct edge{
   int u, v, cost;
   edge(int cu, int cv, int ccost){u=cu, v=cv, cost=ccost;}
   edge(){}
   bool operator<(const edge &cmp) const{
       return cost<cmp.cost;
   }
}E[maxn*4];
 
struct point{
   int x, y, id;
}P[maxn];;
 
bool cmpx(point c1, point c2){return c1.x<c2.x;}
 
bool cmpy(point c1, point c2){return c1.y<c2.y;}
 
int Find(int x){
   return x==fa[x]?x:fa[x]=Find(fa[x]);
}
 
LL Kruskal(){
   for(int i=0;i<=n;i++)fa[i]=i;
   sort(E, E+cnt);
   LL ans=0;
   for(int i=0;i<cnt;i++){
       int fu=Find(E[i].u);
       int fv=Find(E[i].v);
       if(fu!=fv){
           ans+=E[i].cost;
           fa[fu]=fv;
       }
   }
   return ans;
}
 
int main()
{
   while(~scanf("%d", &n)){
       for(int i=0;i<n;i++){
           scanf("%d%d", &P[i].x, &P[i].y);
           P[i].id=i;
       }
       cnt=0;
       sort(P, P+n, cmpx);
       for(int i=1;i<n;i++){
           E[cnt++]=edge(P[i-1].id, P[i].id, P[i].x-P[i-1].x);
       }
       sort(P, P+n, cmpy);
       for(int i=1;i<n;i++){
           E[cnt++]=edge(P[i-1].id, P[i].id, P[i].y-P[i-1].y);
       }
       printf("%lld\n", Kruskal());
   }
   return 0;
}