本文主要是介绍2018东北四省赛 Spin A Web 曼哈顿距离最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
莫队的论文，讲的很清晰
问题描述：给定平面N个点，两边相连的代价为曼哈顿距离，求这些点的最小生成树
按一般想法，prime复杂度O(n^2)，Kruskal复杂度O(n^2 logn)，N很大时，这复杂度要爆炸了
但是最小生成树具有一个性质——环切性质，即如果在一个图中存在一个环，把环中权最大的边删去，那么现在最小生成树的权和
删之前相同，所以很多边都是没用的，可以删去
在平面内，分割成八个区域
可以证明，中心的原点只需和每个区域的一个点相连即可（证明当然是要看莫队的）
所以构造的图中至多有8n条边，复杂度为O(nlogn)
以区域1为例，设原点为O(x0,y0)，另一点P(x1,y1)，则 x1>x0 且 y1-x1 > y0-y1，满足x1+y1最小的点即是最近的点
实现使先将x排序，再将y-x排序，然后用树状数组维护x+y的最小值
然后八个区域转换后可以到区域1，因为是双向边，所以四次转换就可以
第一次直接计算，第二次按y=x翻转，即x与y坐标互换，第三次按x=0翻转，即x坐标为负数，第四次在按y=x翻转，就可以计算了
7231: Spin A Web
时间限制: 1 Sec 内存限制: 128 MB
提交: 127 解决: 24
[提交] [状态] [讨论版] [命题人:admin]
题目描述
We have a canvas divided into grid with H rows and W columns. The square at the ith row from the top and the jth column from the left is represented as (i, j). (i, j) square has two value xi,j and yi,j .
Now we want to merge the squares to a connected web with minimal cost. Two squares can be connected if they are in the same row or column, and the cost of connecting (i0, j0) and (i1, j1) is
|xi0,j0 − xi1,j1 | + |yi0,j0 − yi1,j1 |.
输入
Input is given from Standard Input in the following format:
H W
x1,1 x1,2 . . . x1,W
.
.
xH,1 xH,2 . . . xH,W
y1,1 y1,2 . . . y1,W
.
.
yH,1 yH,2 . . . yH,W
Constraints
1 ≤ H × W ≤ 100000
−108 ≤ xi,j, yi,j ≤ 108(1 ≤ i ≤ H, 1 ≤ j ≤ W )
All of them are integers.
输出
Print one line denotes the minimal cost to merge the square to be a connected web.
样例输入
1 3
1 3 2
1 2 3
样例输出
5这个题只能同行或者同列相连，所以对每行每列求一次
代码：
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;inline int read() {char c;int sum = 0;int f = 1;c = getchar();while (c < '0' || c > '9') {if (c == '-')f = -1;c = getchar();}while (c >= '0' && c <= '9') {sum = sum * 10 + c - '0';c = getchar();}return sum * f;
}struct node {int x, y, pos;friend bool operator<(node a, node b) {if (a.x != b.x)return a.x < b.x;return a.y < b.y;}
} s[maxn];int p[maxn];struct node2 {int u, v, val;friend bool operator<(node2 x, node2 y) {return x.val < y.val;}
} edg[maxn * 8];int tot = 0;
int a[maxn], b[maxn];bool cmp(int a, int b) {if (s[a].x != s[b].x) return s[a].x < s[b].x;return s[a].y < s[b].y;
}bool cmp2(node2 x, node2 y) {return x.val < y.val;
}int value[maxn], poss[maxn];
int fa[maxn];void add(int x, int val, int pos) {for (int i = x; i > 0; i -= (i & (-i))) {if (value[i] > val) {value[i] = val;poss[i] = pos;}}
}int ask(int x, int n) {int ma = inf;int ans = -1;for (int i = x; i <= n; i += (i & (-i))) {if (value[i] < ma) {ma = value[i];ans = poss[i];}}return ans;
}int findd(int x) {return fa[x] == x ? x : fa[x] = findd(fa[x]);
}void Union(int x, int y) {int fx = findd(x);int fy = findd(y);if (fx != fy) {fa[fx] = fy;}
}void mandis(int n) {sort(p, p + n, cmp);for (int i = 0; i < n; i++) {a[i] = b[i] = s[p[i]].y - s[p[i]].x;}sort(b, b + n);int k = unique(b, b + n) - b;for (int i = 1; i <= n; i++) {value[i] = inf;poss[i] = -1;}for (int i = n - 1; i >= 0; i--) {int pp = lower_bound(b, b + k, a[i]) - b + 1;int ans = ask(pp, n);if (ans != -1) {edg[tot].u = s[p[i]].pos;edg[tot].v = s[p[ans]].pos;edg[tot++].val = abs(s[p[i]].x - s[p[ans]].x) + abs(s[p[i]].y - s[p[ans]].y);}add(pp, s[p[i]].x + s[p[i]].y, i);}
}void change(int n) {for (int i = 1; i <= 4; i++) {for (int j = 0; j < n; j++) {if (i == 2 || i == 4)swap(s[p[j]].x, s[p[j]].y);else if (i == 3)s[p[j]].x = -1 * s[p[j]].x;}mandis(n);}
}int main() {int h, w;h = read(), w = read();int id = 1;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {s[i * w + j].x = read();s[i * w + j].pos = id++;}}for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {s[i * w + j].y = read();}}int cnt;for (int i = 0; i < h; i++) {cnt = 0;for (int j = 0; j < w; j++)p[cnt++] = i * w + j;change(cnt);}for (int j = 0; j < w; j++) {cnt = 0;for (int i = 0; i < h; i++) {p[cnt++] = i * w + j;}change(cnt);}for (int i = 1; i <= h * w; i++)fa[i] = i;sort(edg, edg + tot, cmp2);ll ans = 0;for (int i = 0; i < tot; i++) {if (findd(edg[i].u) != findd(edg[i].v)) {Union(edg[i].u, edg[i].v);ans += edg[i].val;}}printf("%lld\n", ans);return 0;
}
这篇关于2018东北四省赛 Spin A Web 曼哈顿距离最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
