【概述】

當(dāng)給出一些二維平面的點(diǎn)時(shí)，記兩點(diǎn)間距離為曼哈頓距離，此時(shí)的最小生成樹，稱為曼哈頓最小距離生成樹。

對(duì)于 n 個(gè)點(diǎn)來說，最樸素的做法是暴力求出所有所有點(diǎn)兩兩之間的曼哈頓距離，然后再跑最小生成樹算法，以得到曼哈頓最小距離生成樹，但這樣來做，由于總邊數(shù)有 n^2 條，時(shí)間復(fù)雜度會(huì)達(dá)到 O(n^3) 或 O(n^2 logn)

對(duì)于 Kruskal 來說，針對(duì)這種曼哈頓距離的 MST 問題，實(shí)際上真正用到的點(diǎn)遠(yuǎn)沒有 n^2 之多。

【原理】

考慮構(gòu)建曼哈頓最小距離生成樹時(shí)，每個(gè)點(diǎn)會(huì)與什么樣的點(diǎn)連邊

以一個(gè)每個(gè)點(diǎn)為原點(diǎn)建立直角坐標(biāo)系，將其均分為八個(gè)象限

以單個(gè)象限 R1 為例：假設(shè)以點(diǎn) A 原點(diǎn)，建立直角坐標(biāo)系，并在 R1 區(qū)域內(nèi)找任意兩點(diǎn) B(x1,y1)、C(x2,y2)，且使得 |AB|<=|BC|

根據(jù) A、B、C 坐標(biāo)可得：|AB|=x1+y1，|AC|=x2+y2，|BC|=|x1-x2|+|y1-y2|

由于 B、C 都在 R1 區(qū)域內(nèi)，那么 y-x>0 且 x>0，分情況討論有：

• x1>x2 且 y1>y2 時(shí)：|AB|>|BC|，與假設(shè)矛盾
• x1>x2 且 y1<=y2 時(shí)：|BC|=x1-x2+y2-y1，|AC|-|BC|=x2+y2-x1+x2-y2+y1=y1-x1+2*x2，由于 y1>y2>x2>x1，，假設(shè) |AC|<|BC|，則有：x1>2*x2+y1，那么? |AB|=x1+y1>2*x2+2*y1，|AC|=x2+y2<2*x2<|AB|，與前提矛盾，故：|AC|≥|BC|
• x1<=x2 且 y1>y2 時(shí)：|BC|=x2-x1+y1-y2，|AC|-|BC|=x2+y2-x2+x1-y1+y2=x1-y1+2*y2，由于 y1>y2>x2>x1，假設(shè) |AC|<|BC|，則有：y1>2*y2+x1，那么 |AB|=x1+y1>2*x1+2*y2，|AC|=x2+y2<2*y2<|AB|，與前提矛盾，故：|AC|≥|BC|
• x1<=x2 且 y1<=y2 時(shí)：由于 |AB|+|BC|=|AC|，因此有 |AC|>=|BC|

綜上，有?|AC|>=|BC|，推廣到 8 個(gè)象限中可得：以一個(gè)每個(gè)點(diǎn)為原點(diǎn)建立直角坐標(biāo)系，將其均分為八個(gè)象限，在每象限內(nèi)只會(huì)向距離該點(diǎn)最近的一個(gè)點(diǎn)連邊。

根據(jù)上述結(jié)論，可以篩選出每個(gè)區(qū)域中最近的點(diǎn)。

由于邊的雙向性，因此只需要針對(duì)一個(gè)點(diǎn)考慮 R1~R4 四個(gè)方向即可，這樣總共最多有 4*n 條邊，此時(shí)再使用 Kruskal 時(shí)，時(shí)間復(fù)雜度僅為 O(nlogn)

考慮點(diǎn) (x,y) 在 R1~R4 四個(gè)象限的條件：

• 若 (x,y) 在 R1，則：x≥xi，y–x≥yi–xi（最近點(diǎn)的 x+y 最小）
• 若 (x,y) 在 R2，則：y≥yi，y–x≤yi–xi（最近點(diǎn)的 x+y 最小）
• 若 (x,y)?在 R3，則：y≤yi，y+x≥yi+xi（最近點(diǎn)的 y–x 最小）
• 若 (x,y) 在 R4，則：x ≥xi，y+x?yi–xi（最近點(diǎn)的 y–x 最小）

因此，利用其中一個(gè)條件用排序，另一個(gè)條件用樹狀數(shù)組或離散化來維護(hù)，從而詢問找最近點(diǎn)

【實(shí)現(xiàn)】

struct BIT{//樹狀數(shù)組int arr[N];int Id[N];void init(){memset(arr,INF,sizeof(arr));memset(Id,-1,sizeof(Id));}int lowbit(int k){return k&(-k);}void update(int pos,int val,int id){while(pos>0){if(arr[pos]>val){arr[pos]=val;Id[pos]=id;}pos-=lowbit(pos);}}int query(int pos,int m){int minval=INF;int ans=-1;while(pos<=m){if(minval>arr[pos]){minval=arr[pos];ans=Id[pos];}pos+=lowbit(pos);}return ans;} }B; struct POS{//區(qū)域int x,y;int id;bool operator<(const POS &rhs) const{if(x!=rhs.x)return x<rhs.x;return y<rhs.y;} }pos[N]; struct Edge{int x,y;int dis;bool operator<(const Edge &rhs)const {return dis<rhs.dis;} }edge[N<<2],resEdge[N<<2]; int edgeTot,resEdgeTot; int father[N]; void build(int n){//在R1區(qū)域中建邊sort(pos,pos+n);int a[N],b[N];for(int i=0;i<n;i++){a[i]=pos[i].y-pos[i].x;b[i]=pos[i].y-pos[i].x;}//離散化sort(b,b+n);int num=unique(b,b+n)-b;B.init();for(int i=n-1;i>=0;i--){int poss=lower_bound(b,b+num,a[i])-b+1;int ans=B.query(poss,num);if(ans!=-1){//建邊edge[edgeTot].x=pos[i].id;edge[edgeTot].y=pos[ans].id;edge[edgeTot].dis=abs(pos[i].x-pos[ans].x)+abs(pos[i].y-pos[ans].y);//曼哈頓距離edgeTot++;}B.update(poss,pos[i].x+pos[i].y,i);} } void manhattan(int n,int k) {for(int dir=1;dir<=4;dir++){//左側(cè)四個(gè)區(qū)域if(dir==2||dir==4){//變換區(qū)域for(int i=0;i<n;i++)swap(pos[i].x,pos[i].y);}else if(dir==3){//變換區(qū)域for(int i=0;i<n;i++)pos[i].x=-pos[i].x;}build(n);//建邊} } int Find(int x) {return father[x]==x?x:father[x]=Find(father[x]); } void kruskal(int n,int k){resEdgeTot=0;for(int i=0;i<=n;i++)father[i]=i;sort(edge,edge+edgeTot);int cnt=n-k;for(int i=0;i<edgeTot;i++) {int x=edge[i].x,y=edge[i].y;int fx=Find(x),fy=Find(y);if(fx!=fy) {cnt--;father[fx]=fy;resEdge[resEdgeTot].x=x;resEdge[resEdgeTot].y=y;resEdge[resEdgeTot].dis=edge[i].dis;resEdgeTot++;}} } int main(){int n,k;scanf("%d%d",&n,&k);edgeTot=0;resEdgeTot=0;for(int i=0;i<n;i++){scanf("%d%d",&pos[i].x,&pos[i].y);pos[i].id=i;}manhattan(n,k);kruskal(n,k);sort(resEdge,resEdge+resEdgeTot);int res=0;for(int i=0;i<resEdgeTot;i++)res+=resEdge[i].dis;printf("MST=%d\n",res);printf("The k-th edge's dis is:%d\n",resEdge[resEdgeTot-k].dis);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的图论 —— 生成树 —— 曼哈顿距离最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。