『算法-ACM竞赛-图论-最小生成树』曼哈顿距离最小生成树

『算法-ACM 竞赛-图论-最小生成树』曼哈顿距离最小生成树

一、参考博客

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

博客：学习总结：最小曼哈顿距离生成树

二、前置知识

1.曼哈顿距离：给定二维平面上的 N 个点，在两点之间连边的代价。（即 distance(P1,P2) = |x1－x2|+|y1－y2|）

2.曼哈顿距离最小生成树问题求什么？求使所有点连通的最小代价。

3.最小生成树

三、具体实现方式

朴素的算法可以用 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。下面我们分情况讨论：

x1>x2 且 y1>y2。这与|AB|≤|AC|矛盾；
x1≤x2 且 y1>y2。此时|BC|=x2-x1+y1-y2，|AC|-|BC|=x2+y2-x2+x1-y1+y2=x1-y1+2y2。由前面各种关系可得 y1>y2>x2>x1。假设|AC|<|BC|即 y1>2y2+x1，那么|AB|=x1+y1>2x1+2y2，|AC|=x2+y2<2*y2<|AB|与前提矛盾，故|AC|≥|BC|；
x1>x2 且 y1≤y2。与 2 同理；
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)的复杂度内解决了。

【回到正题】

一个点把平面分成了 8 个部分：

由上面的废话可知，我们只需要让这个点与每个部分里距它最近的点连边。

拿 R1 来说吧：

如图，i 的 R1 区域里距 i 最近的点是 j。也就是说，其他点 k 都有：

xj + yj <= xk + yk

那么 k 将落在如下阴影部分：

显然，边(i,j), (j,k), (i,k)构成一个环<i,j,k>，而(i,k)一定是最长边，可以被删去。所以我们只连边(i,j)。

为了避免重复加边，我们只考虑 R1~R4 这 4 个区域。（总共加了 4N 条边）

这 4 个区域的点(x,y)要满足什么条件？

如果点(x,y)在 R1，它要满足：x ≥ xi ,y – x ≥ yi – xi（最近点的 x + y 最小）
如果点(x,y)在 R2，它要满足：y ≥ yi ,y – x ≤ yi – xi（最近点的 x + y 最小）
如果点(x,y)在 R3，它要满足：y ≤ yi ,y + x ≥ yi + xi（最近点的 y – x 最小）
如果点(x,y)在 R4，它要满足：x ≥ xi ,y + x ≤ yi – xi（最近点的 y – x 最小）
其中一个条件用排序，另一个条件用数据结构（这种方法很常用），在数据结构上询问，找最近点。因为询问总是前缀或后缀，所以可以用树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pi=acos(-1.0);
const double E=2.718281828459;
const ll mod=1e8+7;
const int INF=0x3f3f3f3f;

int n,k;

struct node{
    int x;
    int y;
    int id;
    bool friend operator<(node a,node b){
        return a.x==b.x?a.y<b.y:a.x<b.x;
        ///保证树状数组更新和查询时不会遗漏
    }
}point[10005];

struct edge{
    int s;
    int e;
    int c;
    bool friend operator<(edge a,edge b){
        return a.c<b.c;
    }
}load[40000];
int sign=0;
int p[10005];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}

void kruskal(){
    for(int i=1;i<=n;i++)
        p[i]=i;
    sort(load+1,load+1+sign);
    int cnt=0;
    for(int i=1;i<=sign;i++){
        int x=find(load[i].s);
        int y=find(load[i].e);
        if(x!=y){
            cnt++;
            p[x]=y;
            if(cnt==n-k){
                printf("%d\n",load[i].c);
                return ;
            }
        }
    }
}

int id[10005]; ///y-x为索引的编号
int xy[10005]; ///y-x为索引 x+y的最小值

void update(int index,int minn,int s)   ///index:y-x  minn:x+y   s:编号
{
    index+=1000;
    for(int i=index;i>=1;i-=(i&(-i))){
        if(xy[i]>minn){
            xy[i]=minn;
            id[i]=s;
        }
    }
}

void query(int index,int minn,int s)    ///index:y-x  minn:x+y   s:编号
{
    index+=1000;
    int e=-1,c=INF;
    ///现在以编号s为原点,查询y-x>=index的点中x+y的最小值
    for(int i=index;i<10000;i+=(i&(-i))){
        if(xy[i]<c){
            e=id[i];
            c=xy[i];
        }
    }
    if(e!=-1)
        load[++sign]=edge{s,e,c-minn};
}

void build_edge()
{
    /// 以(xi,yi)为原点,对于第1区域内的点(x,y)满足条件
    /// x>=xi,y-x>=yi-xi,(x+y)最小
    sort(point+1,point+1+n);
    memset(id,-1,sizeof(id));
    fill(xy,xy+10005,INF);
    ///按照x升序
    ///保证后面查询时,x都比当前的x大
    for(int i=n;i>=1;i--){
        int index=point[i].y-point[i].x;
        int minn=point[i].x+point[i].y;
        query(index,minn,point[i].id);
        update(index,minn,point[i].id);
    }
}

int main()      ///第K大边
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&point[i].x,&point[i].y);
        point[i].id=i;
    }
    ///1象限建边
    build_edge();

    ///2象限建边
    for(int i=1;i<=n;i++)
        swap(point[i].x,point[i].y);
    build_edge();

    ///3象限建边
    for(int i=1;i<=n;i++)
        point[i].x=-point[i].x;
    build_edge();

    ///4象限建边
    for(int i=1;i<=n;i++)
        swap(point[i].x,point[i].y);
    build_edge();
    kruskal();
    return 0;
}

算法 > ACM竞赛 > 图论 > 最小生成树
『算法-ACM竞赛-图论-最小生成树』曼哈顿距离最小生成树
https://chiamzhang.github.io/2024/06/29/『算法-ACM竞赛-图论-最小生成树』曼哈顿距离最小生成树/
Author
Chiam
Posted on
June 29, 2024
Licensed under