POJ 3241 Object Clustering 曼哈顿最小生成树

Object Clustering

Description

We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of object i and object j is defined by d_ij = |a_i- a_j| + |b_i- b_j|, and then we say i is d_ij resemble to j. Now we want to find the minimum value of X, so that we can classify the N objects into K (K < N) groups, and in each group, one object is at most X resemble to another object in the same group, i.e, for every object i, if i is not the only member of the group, then there exists one object j (i ≠ j) in the same group that satisfies d_ij ≤ X

Input

The first line contains two integers N and K. The following N lines each contain two integers a and b, which describe a object.

Output

A single line contains the minimum X.

Sample Input

Sample Output

整个题：就是求manhattan最小生成树

曼哈顿距离最小生成树问题可以简述如下：

给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价。

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

但是事实上，真正有用的边远没有O(N²)条。我们考虑每个点会和其他一些什么样的点连边。可以得出这样一个结论，以一个点为原点建立直角坐标系，在每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。下面我们分情况讨论：

1. x1>x2且y1>y2。这与|AB|≤|AC|矛盾；

2. x1≤x2且y1>y2。此时|BC|=x2-x1+y1-y2，|AC|-|BC|=x2+y2-x2+x1-y1+y2=x1-y1+2*y2。由前面各种关系可得y1>y2>x2>x1。假设|AC|<|BC|即y1>2*y2+x1，那么|AB|=x1+y1>2*x1+2*y2，|AC|=x2+y2<2*y2<|AB|与前提矛盾，故|AC|≥|BC|；

3. x1>x2且y1≤y2。与2同理；

4. 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)的复杂度内解决了。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include<vector>

#include <algorithm>

using namespace std;

const int N = 1e4+, M = 4e4+, mod = 1e9+, inf = 0x3f3f3f3f;

typedef long long ll;

struct ss{

    int u,v,w;

    bool operator < (const ss &b) const

    {

        return w < b.w;

    }

}e[N * ];

int tot =  ,id[N] , mi[N] , pos[N] , x[N], cnt ,  y[N], san[N], fa[N], n ,k;

bool cmp(int i,int j)

{

    if(x[i] != x[j]) return x[i] < x[j];

    else return y[i] < y[j];

}

void add(int u,int v,int w) {

    ++tot;

    e[tot].u = u, e[tot].v = v, e[tot].w = w;

}

int query(int x) {

    int ret = -, ans = inf;

    for(int i = x; i <= cnt; i += i&(-i)) {

        if(mi[i] < ans) ans = mi[i] , ret = pos[i];

    }

    return ret;

}

void update(int x, int c, int p) {

    for(int i = x; i >= ; i -= i&(-i)) if(mi[i] > c) mi[i] = c, pos[i] = p;

}

int haxi(int x) {return lower_bound(san + , san + cnt + , x) - san;}

int dis(int i,int j)

{

    return abs(x[i] - x[j]) + abs(y[i] - y[j]);

}

void Manst() {

    tot = ;

    for(int dir = ; dir < ; ++dir) {

        if(dir ==  || dir == )

            for(int i = ; i <= n; ++i) swap(x[i],y[i]);

        else

            for(int i = ; i <= n; ++i) x[i] = -x[i];

        for(int i = ; i <= n; ++i) id[i] = i;

        sort(id + , id + n + , cmp);

        cnt = ;

        for(int i = ; i <= n; ++i) san[++cnt] = y[i] - x[i];

        sort(san + , san + cnt + );

        cnt = unique(san + , san + cnt + ) - san - ;

        for(int i = ; i <= n; ++i) mi[i] = inf , pos[i] = -;

        for(int i = n; i >= ; --i) {

            int u = haxi(y[id[i]] - x[id[i]]);

            int v = query(u);

            if(v != -) add(id[i], v, dis(id[i], v));

            update(u, x[id[i]] + y[id[i]], id[i]);

        }

    }

}

int finds(int x) {return x==fa[x]?x:fa[x]=finds(fa[x]);}

int main()

{

    while(~scanf("%d%d",&n,&k)) {

        for(int i=;i<=n;i++) scanf("%d%d",&x[i],&y[i]);

        Manst();

        sort(e + , e+ tot + );

        for(int i = ; i <= n; ++i) fa[i] = i;

        k = n - k;

        for(int i = ; i <= tot; ++i)

        {

            int u = e[i].u, v = e[i].v, c = e[i].w;

            if(finds(u) != finds(v)) {

                --k;

                fa[finds(u)] = finds(v);

                if(k ==  ) {

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

                    break;

                }

            }

        }

    }

}

巴特西

POJ 3241 Object Clustering 曼哈顿最小生成树

最新文章

热门文章