最小切比雪夫距离生成树

At 的题太智慧辣！！

挺好用的一个科技，因为切比雪夫和曼哈顿可以互化，所以相当于能解决最小曼哈顿距离生成树（大概

百度搜了一下最小曼哈顿距离生成树，看起来比最小切比雪夫距离生成树复杂。

给出点 \((x_1, y_1)\) 和 \((x_2,y_2)\) 的切比雪夫距离定义式：

最主要的思想：切比雪夫距离的特点就是 \(x\) 和 \(y\) 是分裂开的。那么对于两个点之间的边，没必要去算 \(\min\)，可以连接一条长度为 \(|x_1-x_2|\) 和一条长度为 \(|y_1-y_2|\) 的边，取 \(\min\) 直接交给最小生成树做即可（显然最小生成树不会选择大的那条边）。显然此时可以单独对 \(x\) 和 \(y\) 分别考虑，比原来的 \(\min\) 高明到不知道哪里去了。

ARC076B（模板）：给定 \(n\) 个点，求最小切比雪夫距离生成树。

考虑对 \(n\) 个点先后按照 \(x\) 和 \(y\) 排序，每次排序后连接相邻的两个点（详见代码）。然后直接跑你喜欢的最小生成树算法。

此处用的是 Kruskal。

// Problem: D - Built?
// From: AtCoder - AtCoder Regular Contest 076
// URL: https://atcoder.jp/contests/arc076/tasks/arc076_b
// Time: 2022-06-03 19:50
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 1e5+10;

int n, tot, fa[mxn];
LL ans;

struct node { int x, y, id; } nd[mxn];
struct edge { int u, v, w; } e[mxn*2];

int find(int x) { return fa[x] < 0 ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) {
	int rx = find(x), ry = find(y);
	if(fa[rx] > fa[ry]) swap(rx, ry);
	fa[rx] += fa[ry]; fa[ry] = rx;
}

signed main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d%d", &nd[i].x, &nd[i].y), nd[i].id = i, fa[i] = -1;
	sort(nd+1, nd+n+1, [](node a, node b) { return a.x < b.x; });
	for(int i = 1; i < n; ++i) e[++tot] = {nd[i].id, nd[i+1].id, nd[i+1].x-nd[i].x};
	sort(nd+1, nd+n+1, [](node a, node b) { return a.y < b.y; });
	for(int i = 1; i < n; ++i) e[++tot] = {nd[i].id, nd[i+1].id, nd[i+1].y-nd[i].y};
	sort(e+1, e+tot+1, [](edge a, edge b) { return a.w < b.w; });
	for(int i = 1; i <= tot && n > 1; ++i) {
		auto [u, v, w] = e[i];
		if(find(u) == find(v)) continue;
		else merge(u, v), --n, ans += w;
	}
	printf("%lld\n", ans);
	return 0;
}

还有，我愿称之为 MCDST（Minimum Chebyshev Distance Spanning Tree） 。