TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3074
  • 题目
  • P3074最小生成树7
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    评测说明 : 1s
    问题描述

    平面上给你n个点,你要用平行于坐标轴的线段将他们连接成一棵树,并使线段的总长度最小。

    输入格式

    第一行正整数n
    接下来n行每行两个正整数x,y,表示坐标

    输出格式

    一个树,表示线段总长度的最小值

    样例输入 1

    3
    1 1
    2 2
    1 3

    样例输出 1

    3

    样例输入 2

    6
    2 1
    2 3
    2 4
    2 5
    4 5
    5 2

    样例输出 2

    9

    提示

    样例解释:

           [2,2]
             |
    [1,1]----+----[1,3]
    

    数据范围:
    n<=2000
    1<=x<=500
    1<=y<=8
    保证坐标不重复