题目链接： 51nod1213
题目意思：
二维平面上有n个坐标为整数的点，点x1 y1同点x2 y2之间的距离为：横纵坐标的差的绝对值之和，即：Abs(x1 - x2) + Abs(y1 - y2)（也称曼哈顿距离）。求这N个点所组成的完全图的最小生成树(MST)的边权之和。（直接抄的）
题目思路：
如果直接
O
(
n
2
)
O(n^{2})
O(n2)复杂度建图，求MST就等着吃T吧！
图一
仔细思考，事实上，有用的边没有
n
2
n^2
n2条那么多，有那么一个结论，就是对于一个点A，只有如上八个区域（每45°划分为一个区域，每个区域连一个离A点最近的点就可以了。但是由于对称性，我们只需要考虑右边四个区域就好了。 为什么有这么结论呢？ 我们这么思考这样问题，一个图的MST实际上是一个图的子图，那么一个联通子图的MST如果不是原图MST的子图，那么必然是该联通子图外的节点A，与该联通子图内某一个点B,点A和点B的连边（
e
d
g
e
1
edge_1
edge1）小于该联通子图最小生成树内连接点B的边（
e
d
g
e
2
edge_2
edge2），那么显然我们可以用
e
d
g
e
1
edge_1
edge1替换
e
d
g
e
2
edge_2
edge2，使得该联通子图的MST并不是加上点A以后的联通子图的MST的子图
图二
显然上图BCD子图MST中的BC点在ABCD子图中会被AC代替（也可以说被AB代替）
以上说的好像说的是废话
我们可以看到上图中AD我都没有连，因为它实在太长了，MST不可能包含它（显然可以用BD代替它），对于某一个点周边我们只需要连接离它最近的点就好了，那么问题来了，多远连一个合适呢？为什么是分成八个区域呢？ 我们可以接着思考这么一个问题，如果|AB| + |BC| < |AB| + |AC|, 即|BC| < |AC|，且|AB| < |AC|, 那么显然我们只需要连接|AB|就好了，我试过正着证明证不出来（我太菜了），但是上述情况在图一的①区域是成立，这里可反证，就和其他博客写的一样了 反证的链接 然后就是怎么做才能连上这些边呢？ 以①区域为例： 显然AC这条边是没有用的，因为ABC三个点，AB，BC组成的ABC三个点生成树权值更小。 在某点A的①区域内的点B的特点如下：
Y
B
−
X
B
>
Y
A
−
X
A
Y_B-X_B > Y_A-X_A
YB−XB>YA−XA
X
B
>
X
A
，
且
Y
B
>
Y
A
X_B >X_A，且Y_B >Y_A
XB>XA，且YB>YA
所以我们只需要把所有的点先按照
X
X
X从小到大，
X
X
X相等的时候按照
Y
Y
Y从小到大。然后倒着更新，用线段树维护建图。线段树上维护的下标是离散化以后的
Y
−
X
Y-X
Y−X,值为
X
+
Y
X+Y
X+Y。查询区间最小值就好了。 之后直接跑一个MST就好了，Prim或者Kruskal都可以，我觉得Kruskal比较好。 为了简化代码量，我们需要把通过坐标变换，把其他区间的的变换到①区域操作。 第一次：直接操作不用变换。 第二次：
Y
=
X
Y=X
Y=X对称过去。 第三次：
X
=
0
X=0
X=0对称过去。 第四次：
Y
=
X
Y=X
Y=X对称过去。
代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long LL
;
const LL inf
= 1e15;
class Segtree
{
private
:
vector
<pair
<LL
,LL
> >tr
;
public
:
Segtree(int n
) {
tr
.resize(4 * n
+ 10);
for(auto & i
: tr
) i
.first
= i
.second
= inf
;
}
void updata(int x
, int p
, int L
, int R
, pair
<LL
,LL
>num
) {
if(L
== R
) {
tr
[x
] = min(tr
[x
], num
); return;
}
int M
= (L
+ R
) / 2;
if(p
<= M
) updata(x
<< 1, p
, L
, M
, num
);
else updata(x
<< 1 | 1, p
, M
+ 1, R
, num
);
tr
[x
] = min(tr
[x
<< 1], tr
[x
<< 1 | 1]);
}
pair
<LL
,LL
> query(int x
, int l
, int r
, int L
, int R
) {
if(l
<= L
&& R
<= r
) {
return tr
[x
];
}
int M
= (L
+ R
) / 2;
pair
<LL
,LL
> ans
= {inf
,inf
};
if(l
<= M
) ans
= min(ans
, query(x
<< 1, l
, r
, L
, M
));
if(r
> M
) ans
= min(ans
, query(x
<< 1 | 1, l
, r
, M
+ 1, R
));
return ans
;
}
};
struct Point
{
int x
, y
, id
;
bool operator
<(const Point
& m
) const {
if(x
== m
.x
) return y
< m
.y
;
return x
< m
.x
;
}
};
struct edge
{
LL u
, v
, w
;
bool operator
<(const edge
& a
) const {return w
< a
.w
;}
};
LL
Kruskal(vector
<edge
>& e
, int n
) {
vector
<int> bcj
;
bcj
.resize(n
);
iota(bcj
.begin(), bcj
.end(), 0);
sort(e
.begin(), e
.end());
function
<int(int)>gr
=[&](int k
) {
return k
== bcj
[k
]?k
:bcj
[k
] = gr(bcj
[k
]);
};
LL ans
= 0;
int num
= 0;
for (auto& i
: e
) {
int x
= gr(i
.u
), y
= gr(i
.v
);
if (x
!= y
) {
bcj
[x
] = gr(y
);
ans
+= i
.w
;
num
++;
}
if (num
== n
- 1) break;
}
if (num
== n
- 1) return ans
;
else return -1;
}
int main() {
ios
::sync_with_stdio(false
); cin
.tie(0); cout
.tie(0);
int n
; cin
>> n
;
vector
<Point
>a(n
);
function
<LL(Point
, Point
)>dis
=[&](Point aa
, Point bb
) {
return abs(aa
.x
- bb
.x
) + abs(aa
.y
- bb
.y
);
};
for(int i
= 0; i
< n
; i
++) {
cin
>> a
[i
].x
>> a
[i
].y
;
a
[i
].id
= i
;
}
vector
<edge
>e
;
for(int i
= 0; i
< 4; i
++) {
if(i
== 1 || i
== 3) {
for(auto & j
: a
) swap(j
.x
, j
.y
);
}
else if(i
== 2) {
for(auto & j
: a
) j
.x
= -j
.x
;
}
sort(a
.begin(), a
.end());
vector
<LL
>b
;
for(auto& j
: a
) {
b
.push_back(j
.y
- j
.x
);
}
sort(b
.begin(),b
.end());
b
.erase(unique(b
.begin(), b
.end()),b
.end());
function
<int(LL
)>getid
=[&](LL u
) {
return lower_bound(b
.begin(), b
.end(), u
) - b
.begin() + 1;
};
int sz
= b
.size();
Segtree
st(sz
);
for(int j
= a
.size() - 1; j
>= 0; j
--) {
int p
= getid(a
[j
].y
- a
[j
].x
);
pair
<LL
,LL
>ans
= st
.query(1, p
, sz
, 1, sz
);
if(ans
.first
!= inf
) {
e
.push_back({a
[j
].id
, a
[ans
.second
].id
, dis(a
[j
], a
[ans
.second
])});
}
st
.updata(1, p
, 1, sz
, make_pair(a
[j
].x
+ a
[j
].y
, j
));
}
}
cout
<< Kruskal(e
, n
) << '\n';
return 0;
}
