曼哈顿距离最小生成树与莫队算法

2024-08-24 11:58
文章标签 算法 最小 生成 距离 曼哈顿 莫队

本文主要是介绍曼哈顿距离最小生成树与莫队算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、曼哈顿距离最小生成树

曼哈顿距离最小生成树问题可以简述如下：

给定二维平面上的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)的复杂度内解决了。

 

二、莫队算法

据说这个算法是莫涛提出的（Orz！），但是在网上到处都搜不到相关资料，最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法，其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题（清橙A1206《小Z的袜子》，就是莫队出的题）：

给定一个长为N的序列，每个元素的值是其颜色。有M次询问，每次询问从一个区间中随机选取两个元素同色的概率。

一次询问[l,r]的答案即，其中是区间中第i中颜色的个数。显然暴力是O(NM)的，而且一般的区间问题的思路似乎不适用。

我们先考虑一个简化的问题：所有的查询区间的左端点都是1。那么我们可以按右端点排序，假设已经处理出了[1,r]的答案，考虑转移到[1,r+k]，即添加k个元素，这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度（不考虑排序）就是O(N)。

那么如果是从[l,r]转移到[l’,r’]呢？复杂度即O(|r’-r|+|l’-l|)，也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点，求曼哈顿距离最小生成树，再按照生成树的顺序做，就可以最小化区间之间转移的复杂度。可以证明（我不会证……似乎莫队的论文里有），这样做的复杂度是O(N1.5)的。问题也就得到了解决。



代码：

POJ3241 Object Clustering 求曼哈顿距离最小生成树上第k大的边

[cpp]  view plain copy
  1. //POJ3241; Object Clustering; Manhattan Distance MST  
  2. #include <cstdio>  
  3. #include <cstdlib>  
  4. #include <algorithm>  
  5. #define N 100000  
  6. #define INFI 123456789  
  7.   
  8. struct point  
  9. {  
  10.     int x, y, n;  
  11.     bool operator < (const point &p) const  
  12.     { return x == p.x ? y < p.y : x < p.x; }  
  13. }p[N + 1];  
  14. struct inedge  
  15. {  
  16.     int a, b, w;  
  17.     bool operator < (const inedge &x) const  
  18.     { return w < x.w; }  
  19. }e[N << 3 | 1];  
  20. struct BITnode  
  21. {  
  22.     int w, p;  
  23. }arr[N + 1];  
  24. int n, k, tot = 0, f[N + 1], a[N + 1], *l[N + 1], ans;  
  25.   
  26. template <typename T>  
  27. inline T abs(T x)  
  28. { return x < (T)0 ? -x : x; }  
  29.   
  30. int find(int x)  
  31. { return x == f[x] ? x : f[x] = find(f[x]); }  
  32.   
  33. inline bool cmp(int *a, int *b)  
  34. { return *a < *b; }  
  35.   
  36. inline int query(int x)  
  37. {  
  38.     int r = INFI, p = -1;  
  39.     for (; x <= n; x += x & -x)  
  40.         if (arr[x].w < r) r = arr[x].w, p = arr[x].p;  
  41.     return p;  
  42. }  
  43.   
  44. inline void modify(int x, int w, int p)  
  45. {  
  46.     for (; x > 0; x -= x & -x)  
  47.         if (arr[x].w > w) arr[x].w = w, arr[x].p = p;  
  48. }  
  49.   
  50. inline void addedge(int a, int b, int w)  
  51. {  
  52.     ++tot;  
  53.     e[tot].a = a, e[tot].b = b, e[tot].w = w;  
  54. //  printf("%d %d %d\n", a, b, w);  
  55. }  
  56.   
  57. inline int dist(point &a, point &b)  
  58. { return abs(a.x - b.x) + abs(a.y - b.y); }  
  59.   
  60. int main()  
  61. {  
  62.     //Initialize  
  63.     scanf("%d%d", &n, &k);  
  64.     for (int i = 1; i <= n; ++i)  
  65.     {  
  66.         scanf("%d%d", &p[i].x, &p[i].y);  
  67.         p[i].n = i;  
  68.     }  
  69.     //Solve  
  70.     for (int dir = 1; dir <= 4; ++dir)  
  71.     {  
  72.         //Coordinate transform - reflect by y=x and reflect by x=0  
  73.         if (dir == 2 || dir == 4)  
  74.             for (int i = 1; i <= n; ++i) p[i].x ^= p[i].y ^= p[i].x ^= p[i].y;  
  75.         else if (dir == 3)  
  76.             for (int i = 1; i <= n; ++i) p[i].x = -p[i].x;  
  77.         //Sort points according to x-coordinate  
  78.         std::sort(p + 1, p + n + 1);  
  79.         //Discretize  
  80.         for (int i = 1; i <= n; ++i) a[i] = p[i].y - p[i].x, l[i] = &a[i];  
  81.         std::sort(l + 1, l + n + 1, cmp);  
  82.         /* 
  83.         int cnt = 1; 
  84.         for (int i = 2; i <= n; ++i) 
  85.             if (*l[i] != *l[i - 1]) *l[i - 1] = cnt++; 
  86.             else *l[i - 1] = cnt; 
  87.         *l[n] = cnt; 
  88.         */  
  89.         for (int i = 1; i <= n; ++i) *l[i] = i;  
  90.         //Initialize BIT  
  91.         for (int i = 1; i <= n; ++i) arr[i].w = INFI, arr[i].p = -1;  
  92.         //Find points and add edges  
  93.         for (int i = n; i > 0; --i)  
  94.         {  
  95.             int pos = query(a[i]);  
  96.             if (pos != -1)  
  97.                 addedge(p[i].n, p[pos].n, dist(p[i], p[pos]));  
  98.             modify(a[i], p[i].x + p[i].y, i);  
  99.         }  
  100.     }  
  101.     //Kruskal  
  102.     std::sort(e + 1, e + tot + 1);  
  103.     for (int i = 1; i <= n; ++i) f[i] = i;  
  104.     for (int i = 1, ec = n; ec > k && i <= tot; ++i)  
  105.         if (find(e[i].a) != find(e[i].b))  
  106.         {  
  107.             f[find(e[i].a)] = find(e[i].b);  
  108.             if (--ec == k) ans = e[i].w;  
  109.         }  
  110.     printf("%d\n", ans);  
  111.     return 0;  
  112. }  

Tsinsen A1206 小Z的袜子（其实这题暴力有60分……）

[cpp]  view plain copy
  1. //Tsinsen A1206; 小Z的袜子; Modui Algorithm  
  2. #include <cstdio>  
  3. #include <cstdlib>  
  4. #include <algorithm>  
  5. #define N 50000  
  6. #define Q 50000  
  7. #define INFI 123456789  
  8.   
  9. typedef long long ll;  
  10. struct edge  
  11. {  
  12.     int next, node;  
  13. }e[Q << 1 | 1];  
  14. int head[N + 1], tot = 0;  
  15. struct point  
  16. {  
  17.     int x, y, n;  
  18.     bool operator < (const point &p) const  
  19.     { return x == p.x ? y < p.y : x < p.x; }  
  20. }qt[Q + 1], p[Q + 1];  
  21. struct inedge  
  22. {  
  23.     int a, b, w;  
  24.     bool operator < (const inedge &x) const  
  25.     { return w < x.w; }  
  26. }ie[Q << 3 | 1];  
  27. int cnt = 0;  
  28. struct BITnode  
  29. {  
  30.     int w, p;  
  31. }arr[Q + 1];  
  32. int n, q, col[N + 1], a[Q + 1], *l[Q + 1], f[N + 1], c[N + 1];  
  33. ll cur, ans[Q + 1];  
  34. bool v[Q + 1];  
  35.   
  36. template <typename T>  
  37. inline T abs(T x)  
  38. { return x < (T)0 ? -x : x; }  
  39.   
  40. inline int dist(const point &a, const point &b)  
  41. { return abs(a.x - b.x) + abs(a.y - b.y); }  
  42.   
  43. inline void addinedge(int a, int b, int w)  
  44. {  
  45.     ++cnt;  
  46.     ie[cnt].a = a, ie[cnt].b = b, ie[cnt].w = w;  
  47. }  
  48.   
  49. inline void addedge(int a, int b)  
  50. {  
  51.     e[++tot].next = head[a];  
  52.     head[a] = tot, e[tot].node = b;  
  53. }  
  54.   
  55. inline bool cmp(int *a, int *b)  
  56. { return *a < *b; }  
  57.   
  58. inline int query(int x)  
  59. {  
  60.     int r = INFI, p = -1;  
  61.     for (; x <= q; x += x & -x)  
  62.         if (arr[x].w < r) r = arr[x].w, p = arr[x].p;  
  63.     return p;  
  64. }  
  65.   
  66. inline void modify(int x, int w, int p)  
  67. {  
  68.     for (; x > 0; x -= x & -x)  
  69.         if (arr[x].w > w) arr[x].w = w, arr[x].p = p;  
  70. }  
  71.   
  72. int find(int x)  
  73. { return x == f[x] ? x : f[x] = find(f[x]); }  
  74.   
  75. inline ll calc(int x)  
  76. { return (ll)x * (x - 1); }  
  77.   
  78. inline void add(int l, int r)  
  79. {  
  80.     for (int i = l; i <= r; ++i)  
  81.     {  
  82.         cur -= calc(c[col[i]]);  
  83.         cur += calc(++c[col[i]]);  
  84.     }  
  85. }  
  86.   
  87. inline void remove(int l, int r)  
  88. {  
  89.     for (int i = l; i <= r; ++i)  
  90.     {  
  91.         cur -= calc(c[col[i]]);  
  92.         cur += calc(--c[col[i]]);  
  93.     }  
  94. }  
  95.   
  96. void dfs(int x, int l, int r)  
  97. {  
  98.     v[x] = true;  
  99.     //Process right bound  
  100.     if (r < qt[x].y)  
  101.         add(r + 1, qt[x].y);  
  102.     else if (r > qt[x].y)  
  103.         remove(qt[x].y + 1, r);  
  104.     //Process left bound  
  105.     if (l < qt[x].x)  
  106.         remove(l, qt[x].x - 1);  
  107.     else if (l > qt[x].x)  
  108.         add(qt[x].x, l - 1);  
  109.     ans[x] = cur;  
  110.     //Moving on to next query  
  111.     for (int i = head[x]; i; i = e[i].next)  
  112.     {  
  113.         if (v[e[i].node]) continue;  
  114.         dfs(e[i].node, qt[x].x, qt[x].y);  
  115.     }  
  116.     //Revert changes  
  117.     //Process right bound  
  118.     if (r < qt[x].y)  
  119.         remove(r + 1, qt[x].y);  
  120.     else if (r > qt[x].y)  
  121.         add(qt[x].y + 1, r);  
  122.     //Process left bound  
  123.     if (l < qt[x].x)  
  124.         add(l, qt[x].x - 1);  
  125.     else if (l > qt[x].x)  
  126.         remove(qt[x].x, l - 1);  
  127. }  
  128.   
  129. ll gcd(ll a, ll b)  
  130. { return !b ? a : gcd(b, a % b); }  
  131.   
  132. int main()  
  133. {  
  134.     //Initialize  
  135.     scanf("%d%d", &n, &q);  
  136.     for (int i = 1; i <= n; ++i) scanf("%d", col + i);  
  137.     for (int i = 1; i <= q; ++i) scanf("%d%d", &qt[i].x, &qt[i].y);  
  138.   
  139.     //Manhattan MST  
  140.     for (int i = 1; i <= q; ++i) p[i] = qt[i], p[i].n = i;  
  141.     for (int dir = 1; dir <= 4; ++dir)  
  142.     {  
  143.         //Coordinate transform  
  144.         if (dir == 2 || dir == 4)  
  145.             for (int i = 1; i <= q; ++i) std::swap(p[i].x, p[i].y);  
  146.         else if (dir == 3)  
  147.             for (int i = 1; i <= q; ++i) p[i].x = -p[i].x;  
  148.         //Sort by x-coordinate  
  149.         std::sort(p + 1, p + q + 1);  
  150.         //Discretize  
  151.         for (int i = 1; i <= q; ++i) a[i] = p[i].y - p[i].x, l[i] = &a[i];  
  152.         std::sort(l + 1, l + q + 1, cmp);  
  153.         int cnt = 1;  
  154.         for (int i = 2; i <= q; ++i)  
  155.             if (*l[i] == *l[i - 1]) *l[i - 1] = cnt;  
  156.             else *l[i - 1] = cnt++;  
  157.         *l[q] = cnt;  
  158.         //Initialize BIT  
  159.         for (int i = 1; i <= q; ++i) arr[i].w = INFI, arr[i].p = -1;  
  160.         //Find points and add edges  
  161.         for (int i = q; i > 0; --i)  
  162.         {  
  163.             int pos = query(a[i]);  
  164.             if (pos != -1)  
  165.                 addinedge(p[i].n, p[pos].n, dist(p[i], p[pos]));  
  166.             modify(a[i], p[i].x + p[i].y, i);  
  167.         }  
  168.     }  
  169.     //Kruskal  
  170.     std::sort(ie + 1, ie + cnt + 1);  
  171.     //Initialize disjoint set  
  172.     for (int i = 1; i <= q; ++i) f[i] = i;  
  173.     //Add edges  
  174.     for (int i = 1; i <= cnt; ++i)  
  175.         if (find(ie[i].a) != find(ie[i].b))  
  176.         {  
  177.             f[find(ie[i].a)] = find(ie[i].b);  
  178.             addedge(ie[i].a, ie[i].b), addedge(ie[i].b, ie[i].a);  
  179.         }  
  180.   
  181.     //Modui Algorithm  
  182.     ++c[col[1]];  
  183.     dfs(1, 1, 1);  
  184.       
  185.     //Output  
  186.     for (int i = 1; i <= q; ++i)  
  187.     {  
  188.         ll x = ans[i], y = calc(qt[i].y - qt[i].x + 1);  
  189.         if (!x) printf("0/1\n");  
  190.         else  
  191.         {  
  192.             ll g = gcd(x, y);  
  193.             printf("%I64d/%I64d\n", x / g, y / g);  
  194.         }  
  195.     }  
  196.   
  197.     return 0;  
  198. }  

这篇关于曼哈顿距离最小生成树与莫队算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1102416。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
poj 1287 Networking（prim or kruscal最小生成树）

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。 注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2