曼哈顿最小生成树

莫涛大神的论文
曼哈顿距离最小生成树问题可以简述如下：
给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。

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

朴素的算法可以用O(n^2)的Prim，或者处理出所有边做Kruskal，但在这里总边数有O( n^2)条，所以Kruskal的复杂度变成了O( n^2logn)。

而莫涛的算法时间复杂度是nlogn

莫队算法步骤

算法步骤：
先将点按x坐标升序排序；
以任一一个点为端点，将平面分为八块，每块占45度角，那么在生成树的最优解中，每个块与这个点至多有一条边，即一个点最多分别向八个方向最近的点连接一条边，一条边两个点共用，同时，有四个方向是两两对称的，所以只需要求出四块（一般求第一象限和第四象限）所以最后边数为4 * n。

B - 曼哈顿最小生成树
题意;
求曼哈顿最小生成树的第n-k条边的权值
题解：
实现一：线段树＋莫队算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=10010;
const int MAXE=4*MAXN;
/*Kruskal  Algorithm*/
int parent[MAXN];
int father(int u)
{
    while(parent[u]!=u)
    {
        parent[u]=parent[parent[u]];
        u=parent[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=father(u);
    int fv=father(v);
    if(fv==fu) return false;
    parent[fu]=fv;
    return true;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator<(const Edge &ee)const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
/*线段树  */
struct Point
{
    int x,y,id;
    bool operator<(const Point &t) const
    {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
Point point[MAXN];
const int INF=0x3f3f3f3f;
struct Node
{
    int len,id;
};
Node tree[(MAXN+20)<<2];
void build(int l,int r,int rt)//init tree
{
    tree[rt].len=INF;
    tree[rt].id=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int rt,Point &p,int pos)//push Point into tree
{
    if(l==r)
    {
        if(tree[rt].len>p.x+p.y)//be careful
        {
            tree[rt].len=p.x+p.y;
            tree[rt].id=p.id;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,rt<<1,p,pos);
    else update(mid+1,r,rt<<1|1,p,pos);
    if(tree[rt<<1].len<tree[rt<<1|1].len)
    {
        tree[rt].len=tree[rt<<1].len;
        tree[rt].id=tree[rt<<1].id;
    }
    else
    {
        tree[rt].len=tree[rt<<1|1].len;
        tree[rt].id=tree[rt<<1|1].id;
    }
}
Node query(int l,int r,int L,int R,int rt)//从大于point[i].y-point[i].x的节点找最小值
{
    if(l==L&&r==R) return tree[rt];
    int mid=(l+r)>>1;
    if(R<=mid) return query(l,mid,L,R,rt<<1);
    else if(L>=mid+1) return query(mid+1,r,L,R,rt<<1|1);
    else
    {
        Node t1=query(l,mid,L,mid,rt<<1);
        Node t2=query(mid+1,r,mid+1,R,rt<<1|1);
        if(t1.len<t2.len) return t1;
        else return t2;
    }
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=point[i].y-point[i].x;
        cpy[i]=arr[i];
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;//离散化
    }
    build(1,n,1);
    for(int i=n;i>0;i--)
    {
        int len=point[i].x+point[i].y;
        Node t=query(1,n,arr[i],n,1);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(len-t.len));
        update(1,n,1,point[i],arr[i]);
    }
}
/*Kruskal  Algorithm*/
int kruskal_mst(int k,int n)
{
    int u,v,sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum++;
            if(sum==n-k) return edge[i].w;
        }
    }
}
int main()
{
    int n,k;
    cnt=0;
    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;
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    solve(n);//第一象限左上角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);//第一象限右下角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);//第四象限左下角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);//第四象限右上角
    printf("%d\n",kruskal_mst(k,n));
}

实现二：
树状数组＋莫队算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=MAXN*4;
const int INF=0x3f3f3f3f;
/*kruskal alrorithm*/
int father[MAXN],n;
int parent(int u)
{
    while(father[u]!=u)
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=parent(u);
    int fv=parent(v);
    if(fu==fv) return false;
    father[fu]=fv;
    return true;
}
struct Point
{
    int x,y,id;//id is for union_found
    bool operator <(const Point &p) const
    {
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
};
Point point[MAXN];
/*数状数组*/
struct Node
{
    int len,id;//len is to find min(x+y), id is for union_found
    void init(){len=INF;id=-1;}
};
Node c[MAXN<<2];
/*倒叙的树状数组，求的是后缀*/
void add(int x,Point &p)//push point into tree
{
    int len=p.x+p.y;
    while(x>0)
    {
        if(c[x].len>len)
        {
            c[x].id=p.id;
            c[x].len=len;
        }
        x-=x&(-x);
    }
}
/*在区间[x,y]求最小值*/
Node query(int x,int y)//从大于point[i].y-point[i].x的节点找最小值
{
    Node t;t.init();
    while(x<=y)
    {
        if(t.len>c[x].len)
        {
            t=c[x];
        }
        x+=x&(-x);
    }
    return t;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator <(const Edge &ee) const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=cpy[i]=point[i].y-point[i].x;
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    for(int i=1;i<=cc;i++) c[i].init();
    for(int i=n;i>0;i--)
    {
        Node t=query(arr[i],cc);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(point[i].x+point[i].y-t.len));
        add(arr[i],point[i]);
    }
}
long long kruskal_mst(int k)
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum++;
            if(sum==n-k) return edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int 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;
    }
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    cnt=0;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    printf("%lld\n",kruskal_mst(k));
}

C - Another Minimum Spanning Tree
题意：
求解曼哈顿最小生成树
线段树＋莫队算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=4*MAXN;
/*Kruskal  Algorithm*/
int parent[MAXN];
int father(int u)
{
    while(parent[u]!=u)
    {
        parent[u]=parent[parent[u]];
        u=parent[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=father(u);
    int fv=father(v);
    if(fv==fu) return false;
    parent[fu]=fv;
    return true;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator<(const Edge &ee)const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
/*线段树  */
struct Point
{
    int x,y,id;
    bool operator<(const Point &t) const
    {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
Point point[MAXN];
const int INF=0x3f3f3f3f;
struct Node
{
    int len,id;
};
Node tree[(MAXN+20)<<2];
void build(int l,int r,int rt)//init tree
{
    tree[rt].len=INF;
    tree[rt].id=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int rt,Point &p,int pos)//push Point into tree
{
    if(l==r)
    {
        if(tree[rt].len>p.x+p.y)
        {
            tree[rt].len=p.x+p.y;
            tree[rt].id=p.id;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,rt<<1,p,pos);
    else update(mid+1,r,rt<<1|1,p,pos);
    if(tree[rt<<1].len<tree[rt<<1|1].len)
    {
        tree[rt].len=tree[rt<<1].len;
        tree[rt].id=tree[rt<<1].id;
    }
    else
    {
        tree[rt].len=tree[rt<<1|1].len;
        tree[rt].id=tree[rt<<1|1].id;
    }
}
Node query(int l,int r,int L,int R,int rt)//从大于point[i].y-point[i].x的节点找最小值
{
    if(l==L&&r==R) return tree[rt];
    int mid=(l+r)>>1;
    if(R<=mid) return query(l,mid,L,R,rt<<1);
    else if(L>=mid+1) return query(mid+1,r,L,R,rt<<1|1);
    else
    {
        Node t1=query(l,mid,L,mid,rt<<1);
        Node t2=query(mid+1,r,mid+1,R,rt<<1|1);
        if(t1.len<t2.len) return t1;
        else return t2;
    }
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=point[i].y-point[i].x;
        cpy[i]=arr[i];
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;//离散化
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    build(1,n,1);
    for(int i=n;i>0;i--)
    {
        int len=point[i].x+point[i].y;
        Node t=query(1,n,arr[i],n,1);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(len-t.len));
        update(1,n,1,point[i],arr[i]);
    }
}
/*Kruskal  Algorithm*/
int kruskal_mst(int n)
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum+=(long long) edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int n,cas=1;
    while(scanf("%d",&n)!=EOF,n){
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&point[i].x,&point[i].y);
        point[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    printf("Case %d: Total Weight = %lld\n",cas++,kruskal_mst(n));
    }
}

树状数组＋莫队算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=MAXN*4;
const int INF=0x3f3f3f3f;
/*kruskal alrorithm*/
int father[MAXN],n;
int parent(int u)
{
    while(father[u]!=u)
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=parent(u);
    int fv=parent(v);
    if(fu==fv) return false;
    father[fu]=fv;
    return true;
}
struct Point
{
    int x,y,id;//id is for union_found
    bool operator <(const Point &p) const
    {
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
};
Point point[MAXN];
/*数状数组*/
struct Node
{
    int len,id;//len is to find min(x+y), id is for union_found
    void init(){len=INF;id=-1;}
};
Node c[MAXN<<2];
/*倒叙的树状数组，求的是后缀*/
void add(int x,Point &p)//push point into tree
{
    int len=p.x+p.y;
    while(x>0)
    {
        if(c[x].len>len)
        {
            c[x].id=p.id;
            c[x].len=len;
        }
        x-=x&(-x);
    }
}
/*在区间[x,y]求最小值*/
Node query(int x,int y)//从大于point[i].y-point[i].x的节点找最小值
{
    Node t;t.init();
    while(x<=y)
    {
        if(t.len>c[x].len)
        {
            t=c[x];
        }
        x+=x&(-x);
    }
    return t;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator <(const Edge &ee) const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=cpy[i]=point[i].y-point[i].x;
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    for(int i=1;i<=cc;i++) c[i].init();
    for(int i=n;i>0;i--)
    {
        Node t=query(arr[i],cc);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(point[i].x+point[i].y-t.len));
        add(arr[i],point[i]);
    }
}
long long kruskal_mst()
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum+=(long long) edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int cas=1;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&point[i].x,&point[i].y);
            point[i].id=i;
        }
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
        }
        cnt=0;
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y;
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y,swap(point[i].x,point[i].y);
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y;
        solve(n);
        printf("Case %d: Total Weight = %lld\n",cas++,kruskal_mst());
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,547评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,399评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,428评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,599评论 1赞 274
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,612评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,577评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,941评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,603评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,852评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,605评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,693评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,375评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,955评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,936评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,172评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,970评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,414评论 2赞 342

推荐阅读更多精彩内容

  • 《大话数据结构》总结
    第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,735评论 0赞 19
  • 数据结构与算法--最小生成树之Prim算法
    数据结构与算法--最小生成树之Prim算法 加权图是一种为每条边关联一个权值或称为成本的图模型。所谓生成树，是某图...
    sunhaiyu阅读 2,064评论 0赞 7
  • SHOW YOUR WORK
    今天看完了《SHOW YOUR WORK》。。。。。。。的中文版，英文版的实在太难啃，没有啃下来，为了不错过好书，...
    我是美美美新阅读 5,629评论 1赞 3