AtCoder ARC 076D

传送门：http://arc076.contest.atcoder.jp/tasks/arc076_b

本题是一个图论问题——Manhattan距离最小生成树（MST）。

在一个平面网格上有n个格点，第i个格点的坐标是(x_i,y_i)，构造一条连接点(a,b)和点(c,d)的边的代价是min{|a-c|,|b-d|}。对给定的n个格点构造连通图，使得总代价最小。

这是一个最小生成树（MST）问题。最“简单”的方法是，由n个结点构造一个无向完全图K_n，之后用Prim算法生成MST。这个程序的时间复杂度为O(n²logn)，空间复杂度为O(n²)。对于10⁵的数据规模，这个方法显然是不可取的。

考虑到Kruskal算法和Prim算法的时间复杂度均为O(ElogV)，应尽可能地降低E的数量级（从Θ(n²)降至Θ(n)）。

考虑以下的构造方式：对于点(a,b)和点(c,d)，不构造代价为min{|a-c|,|b-d|}的边，而是构造两条边，其中一条边的代价为|a-c|，另一条边的代价为|b-d|。设存在i,j,k，使得x_i<x_j<x_k，则连接i和k的代价为|x_i-x_k|的边一定不会出现在MST中。因此，只需在坐标上相邻的两个结点之间构造边即可。这个构造方式构造的边数E=2(n-1)，是Θ(n)的。具体的构造方式如下：

a.对结点按x坐标排序，在每一对相邻的点之间构造一条边，代价是相邻两点距离的x分量；

b.对结点按y坐标排序，在每一对相邻的点之间构造一条边，代价是相邻两点距离的y分量；

构造边的时间复杂度为O(nlogn)，空间复杂度为O(n)。

之后，用Kruskal算法生成MST，时间复杂度为O(nlogn)。参考程序如下：

#include <bits/stdc++.h>

using namespace std;

#define MAX_N 100010

struct point {int id, x, y;};

struct edge {int u, v, w;};

int n;

point p[MAX_N];

edge edgeset[ * MAX_N];

//disjoint set

int pa[MAX_N];

int rnk[MAX_N];

void init(void)

{

    memset(pa, , sizeof(pa));

    memset(rnk, , sizeof(rnk));

    for (int i = ; i < n; i++) {

        pa[i] = i;

        rnk[i] = ;

    }

}

int find(int x)

{

    if (pa[x] == x) return x;

    else return pa[x] = find(pa[x]);

}

void unite(int x, int y)

{

    x = find(x);

    y = find(y);

    if (x == y) return;

    if (rnk[x] < rnk[y]) pa[x] = y;

    else {

        pa[y] = x;

        if (rnk[x] == rnk[y]) rnk[x]++;

    }

}

bool same(int x, int y)

{

    return (find(x) == find(y));

}

int abs(int a)

{

    return a >= ? a: -a;

}

bool cmp_x(point a, point b)

{

    return a.x < b.x;

}

bool cmp_y(point a, point b)

{

    return a.y < b.y;

}

bool cmp_edge(edge a, edge b)

{

    return a.w < b.w;

}

//kruskal minimum spanning tree

int mst(void)

{

    init();

    int res = ;

    for (int i = ; i <  * (n - ); i++) {

        edge e = edgeset[i];

        if (!same(e.u, e.v)) {

            unite(e.u ,e.v);

            res += e.w;

        }

    }

    return res;

}

int main(void)

{

    scanf("%d", &n);

    for (int i = ; i < n; i++) {

        scanf("%d%d", &p[i].x, &p[i].y);

        p[i].id = i;

    }

    sort(p, p + n, cmp_x);

    for (int i = ; i < n - ; i++) {

        edgeset[i].u = p[i].id;

        edgeset[i].v = p[i + ].id;

        edgeset[i].w = abs(p[i + ].x - p[i].x);

    }

    sort(p, p + n, cmp_y);

    for (int i = ; i < n - ; i++) {

        edgeset[i + n - ].u = p[i].id;

        edgeset[i + n - ].v = p[i + ].id;

        edgeset[i + n - ].w = abs(p[i + ].y - p[i].y);

    }

    sort(edgeset, edgeset +  * (n - ), cmp_edge);

    printf("%d\n", mst());

    return ;

}

巴特西

AtCoder ARC 076D - Built?

最新文章

热门文章