题目链接：点击打开链接
题意：
给定二维平面的n个点坐标，，问曼哈顿MST 的值。
模版题
#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 = 1e9;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;typedef long long ll;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);}ll work(){//计算最小生成树，返回花费sort(edge, edge + tot);ll cost = 0;for (int i = 0; i < tot; i++)if (Union(edge[i].from, edge[i].to))cost += edge[i].dis;return cost;}}mst;struct Point{//二维平面的点int x, y, id;bool operator < (const Point&a) const{return x == a.x ? y < a.y : x < a.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 x, int val, int _id){while (x){if (val < c[x]){ c[x] = val; id[x] = _id; }x -= lowbit(x);}}int query(int x){int val = inf, _id = -1;while (x <= maxn){if (val > c[x]){ val = c[x]; _id = id[x]; }x += lowbit(x);}return _id;}}tree;inline bool cmp(int *x, int *y){ return *x < *y; }class Manhattan_MST{int A[N], B[N];public:ll work(int l, int r){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].y = -p[i].y;sort(p + l, p + r + 1);for (int i = l; i <= r; i++) A[i] = B[i] = p[i].y – p[i].x; //离散化sort(B + 1, B + N + 1);int sz = unique(B + 1, B + N + 1) – B – 1;//初始化反树状数组tree.init(sz);for (int i = r; i >= l; i–){int pos = lower_bound(B + 1, B + sz + 1, A[i]) – B;int id = tree.query(pos);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(pos, p[i].x + p[i].y, i);}}return mst.work();}}m_mst;int n;int main(){int Cas = 1;while (cin >> n, n){for (int i = 1; i <= n; i++)rd(p[i].x), rd(p[i].y), p[i].id = i;printf("Case %d: Total Weight = ", Cas++);cout << m_mst.work(1, n) << endl;}return 0;}
人的一辈子唯一做的就是，不断地用你手中
