题目描述

There are N towns on a plane. The i-th town is located at the coordinates (xi,yi). There may be more than one town at the same coordinates.
You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a−c|,|b−d|) yen (the currency of Japan). It is not possible to build other types of roads.
Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints
2≤N≤10 5
0≤xi,yi≤10 9
All input values are integers.

 

输入

Input is given from Standard Input in the following format:

N
x1 y1
x2 y2
:
xN yN

 

输出

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

 

样例输入

3
1 5
3 9
7 8

 

样例输出

3

 

提示

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

今日大凶......总之审题，数据范围都弄不清了

这题初看感觉是最短路，但是每个点连起来就是1e10了

题意是把每个点连起来，需要花费多少，花费就是min(|a−c|,|b−d|)

所以并不需要计算每个点的距离，只需x和y分别排序一下就好，最短距离只有可能从按大小排序的这些点的距离选

然后是Kruskal算法 https://blog.csdn.net/liangzhaoyang1/article/details/51169090

（1） 将全部边按照权值由小到大排序。
（2） 按顺序（边权由小到大的顺序）考虑每条边，只要这条边和我们已经选择的边不构成圈，就保留这条边，否则放弃这条边。

 

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e5+7;
int book[maxn],n;
//
void init()
{
    for(int i=1;i<=n;i++) book[i]=i;
}
int getfa(int x){
    if(book[x]!=x) book[x]=getfa(book[x]);
    return book[x];
}
void mergexy(int x,int y)
{
     book[y]=x;
}
//
struct flv
{
    int u,v,z;
}f[maxn*2];
struct node
{
    int x,y,num;
}s[maxn];
bool cmp1(node a,node b)
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.y<b.y;
}
bool cmp3(flv a,flv b)
{
    return a.z<b.z;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&s[i].x,&s[i].y);
        s[i].num=i;
    }
    sort(s+1,s+n+1,cmp1);
    int cnt=0;
    for(int i=1;i<n;i++){
        f[++cnt].u=s[i].num;
        f[cnt].v=s[i+1].num;
        f[cnt].z=min(s[i+1].x-s[i].x,abs(s[i+1].y-s[i].y));
    }
    sort(s+1,s+n+1,cmp2);
    for(int i=1;i<n;i++){
        f[++cnt].u=s[i].num;
        f[cnt].v=s[i+1].num;
        f[cnt].z=min(s[i+1].y-s[i].y,abs(s[i+1].x-s[i].x));
    }
    sort(f+1,f+cnt+1,cmp3);
    init();
    int number=0;
    int sum=0;
    for(int i=1;i<=cnt;i++){
        int p=getfa(f[i].u),q=getfa(f[i].v);
        if(p!=q){
            mergexy(p,q);
            number++;
            sum+=f[i].z;
        }
        if(number==n) break;
    }
    printf("%d\n",sum);
    return 0;
}
View Code