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

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。

相关文章

nginx生成自签名SSL证书配置HTTPS的实现

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-
阅读更多...
Java实战之利用POI生成Excel图表

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图（Line Ch
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
浅析如何使用Swagger生成带权限控制的API文档

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里，API
阅读更多...
Java使用POI-TL和JFreeChart动态生成Word报告

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

《Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南》在日常数据处理工作中,我们经常需要将不同Excel文档中的数据整合到一个新的DataFrame中,以便进行进一步... 目录一、准备工作二、读取Excel文件三、数据叠加四、处理重复数据（可选）五、保存新DataFram
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2