题目链接：点击打开链接
题意：
给定二维平面上的n个点坐标，常数k
下面n行给出坐标
求一个最小生成树，问第k大的边是多少。
任意两个点间建一条边的花费是其曼哈顿距离。
思路：转自：点击打开链接
一、曼哈顿距离最小生成树
曼哈顿距离最小生成树问题可以简述如下：
给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。
朴素的算法可以用O(N2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O(N2)条，所以Kruskal的复杂度变成了O(N2logN)。
但是事实上，真正有用的边远没有O(N2)条。我们考虑每个点会和其他一些什么样的点连边。可以得出这样一个结论，以一个点为原点建立直角坐标系，在每45度内只会向距离该点最近的一个点连边。
这个结论可以证明如下：假设我们以点A为原点建系，考虑在y轴向右45度区域内的任意两点B(x1,y1)和C(x2,y2)，不妨设|AB|≤|AC|（这里的距离为曼哈顿距离），如下图：
|AB|=x1+y1，|AC|=x2+y2，|BC|=|x1-x2|+|y1-y2|。而由于B和C都在y轴向右45度的区域内，有y-x>0且x>0。下面我们分情况讨论：
1.x1>x2且y1>y2。这与|AB|≤|AC|矛盾；
2.x1≤x2且y1>y2。此时|BC|=x2-x1+y1-y2，|AC|-|BC|=x2+y2-x2+x1-y1+y2=x1-y1+2*y2。由前面各种关系可得y1>y2>x2>x1。假设|AC|<|BC|即y1>2*y2+x1，那么|AB|=x1+y1>2*x1+2*y2，|AC|=x2+y2<2*y2<|AB|与前提矛盾，故|AC|≥|BC|；
3.x1>x2且y1≤y2。与2同理；
4.x1≤x2且y1≤y2。此时显然有|AB|+|BC|=|AC|，，即有|AC|>|BC|。
综上有|AC|≥|BC|，也即在这个区域内只需选择距离A最近的点向A连边。
这种连边方式可以保证边数是O(N)的，那么如果能高效处理出这些边，就可以用Kruskal在O(NlogN)的时间内解决问题。下面我们就考虑怎样高效处理边。
我们只需考虑在一块区域内的点，其他区域内的点可以通过坐标变换“移动”到这个区域内。为了方便处理，我们考虑在y轴向右45度的区域。在某个点A(x0,y0)的这个区域内的点B(x1,y1)满足x1≥x0且y1-x1>y0-x0。这里对于边界我们只取一边，但是操作中两边都取也无所谓。那么|AB|=y1-y0+x1-x0=(x1+y1)-(x0+y0)。在A的区域内距离A最近的点也即满足条件的点中x+y最小的点。因此我们可以将所有点按x坐标排序，再按y-x离散，用线段树或者树状数组维护大于当前点的y-x的最小的x+y对应的点。时间复杂度O(NlogN)。
至于坐标变换，一个比较好处理的方法是第一次直接做；第二次沿直线y=x翻转，即交换x和y坐标；第三次沿直线x=0翻转，即将x坐标取相反数；第四次再沿直线y=x翻转。注意只需要做4次，因为边是双向的。
至此，整个问题就可以在O(NlogN)的复杂度内解决了。
#include <stdio.h>#include <iostream>#include <algorithm>#include <sstream>#include <stdlib.h>#include <string.h>#include <limits.h>#include <vector>#include <string>#include <time.h>#include <math.h>#include <iomanip>#include <queue>#include <stack>#include <set>#include <map>const int inf = 1e8;const double eps = 1e-8;const double pi = acos(-1.0);template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) { putchar('-'); x = -x; }if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int N = 1e5 + 10;class MST{struct Edge{int from, to, dis;Edge(int _from = 0, int _to = 0, int _dis = 0) :from(_from), to(_to), dis(_dis){}bool operator < (const Edge &x) const{return dis < x.dis;}}edge[N << 3];int f[N], tot;int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); }bool Union(int x, int y){x = find(x); y = find(y);if (x == y)return false;if (x > y)swap(x, y);f[x] = y;return true;}public:void init(int n){for (int i = 0; i <= n; i++)f[i] = i;tot = 0;}void add(int u, int v, int dis){edge[tot++] = Edge(u, v, dis);}int work(){sort(edge, edge + tot);int cost = 0;for (int i = 0; i < tot; i++){if (Union(edge[i].from, edge[i].to))cost += edge[i].dis;}return cost;}int work_kth(int k){sort(edge, edge + tot);int cost = 0;for (int i = 0; i < tot && k; i++){if (Union(edge[i].from, edge[i].to))cost = edge[i].dis, k–;}return cost;}}mst;struct Point{int x, y, id;friend bool operator<(const Point&a, const Point&b){if (a.x == b.x)return a.y < b.y;return a.x < b.x;}}p[N];class BIT{int c[N], id[N], maxn;int lowbit(int x){ return x&-x; }public:void init(int n){maxn = n + 10;fill(c, c + maxn + 1, inf);fill(id, id + maxn + 1, -1);}void updata(int pos, int val, int _id){while (pos){if (c[pos] > val){ c[pos] = val; id[pos] = _id; }pos -= lowbit(pos);}}int query(int pos){int val = inf, _id = -1;while (pos <= maxn){if (val > c[pos]){ val = c[pos]; _id = id[pos]; }pos += lowbit(pos);}return _id;}}tree;inline bool cmp(int *x, int *y){ return *x < *y; }class Manhattan_MST{int *po[N], a[N]; public:int work(int l, int r, int k){mst.init(r);for (int dir = 1; dir <= 4; dir++){if (dir%2==0)for (int i = l; i <= r; i++)swap(p[i].x, p[i].y);else if (dir == 3)for (int i = l; i <= r; i++)p[i].x = -p[i].x;sort(p + l, p + r + 1);for (int i = l; i <= r; ++i) a[i] = p[i].y – p[i].x, po[i] = &a[i];sort(po + l, po + r + 1, cmp);for (int i = l; i <= r; i++)*po[i] = i;tree.init(r);for (int i = r; i >= l; i–){int id = tree.query(a[i]);if (id != -1)mst.add(p[i].id, p[id].id, abs(p[i].x – p[id].x) + abs(p[i].y – p[id].y));tree.updata(a[i], p[i].x + p[i].y, i);}}return mst.work_kth(k);}}m_mst;int n, k;int main(){rd(n); rd(k);for (int i = 1; i <= n; i++)rd(p[i].x), rd(p[i].y), p[i].id = i;pt(m_mst.work(1, n, n-k)); puts("");return 0;}
世上再美的风景，都不及回家的那段路。
