曼哈顿最小生成树

莫涛大神的论文
曼哈顿距离最小生成树问题可以简述如下：
给定二维平面上的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());
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

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