【poj3241】Object Clustering

2015.04.15 17:03 Wed | 14次阅读 | 旧日oi | 固定链接 | 源码

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 dij = |ai _- aj_| + |bi _- bj_|, and then we say i is dij 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 dijX
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
6 2
1 2
2 3
2 2
3 4
4 3
3 1
Sample Output
2
题解
求曼哈顿距离mst,然后求前k小的边
裸模板,网上教程太多了,不写了,记住就行了。
ps.linux下的异或操作和windows下好像略有不同……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,k;
struct Point{
    int x,y;
    int idx;
}p[maxn];
struct edge{
    int u,v,len;
}e[maxn*10];
int ed;
int a[maxn];
pair<int,int *> b[maxn];
bool cmp2(const edge &a,const edge &b)
{
    return a.len<b.len;
}
int fa[maxn];
int find(int x)
{
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
int ans[maxn];
void Kruskal()
{
    for(int i=1;i<=n;i++) fa[i]=i;
    int ans=0;
    sort(e+1,e+ed+1,cmp2);
        for (int i = 1, ec = n; ec > k && i <= ed; i++)
        if (find(e[i].u) != find(e[i].v))
        {
            fa[find(e[i].u)] = find(e[i].v);
            if (--ec == k) ans = e[i].len;
        }
        cout<<ans;
}
bool cmp(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
struct BIT{
    int w,r;
}c[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int w,int r)
{
    for(;x;x-=lowbit(x))
    {
        if(c[x].w>w) 
            c[x].w=w,c[x].r=r;
    }
}
int query(int x)
{
    int r=inf,p=-1;
    for(;x<=n;x+=lowbit(x))
        if(c[x].w<r) 
            r=c[x].w,p=c[x].r;
    return p;
}
int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)
    {
        p[i].x=read();
        p[i].y=read(); 
        p[i].idx=i;
    }
    for(int t=1;t<=4;t++)
    {
        if(t%2==0) 
            for(int i=1;i<=n;i++) swap(p[i].x,p[i].y);
        if (t==3)
            for(int i=1;i<=n;i++) p[i].x=-p[i].x;
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++) 
            b[i]=make_pair(p[i].y-p[i].x,a+i);
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++) 
            *b[i].second=i;
        for(int i=1;i<=n;i++)
            c[i].w=inf,c[i].r=-1;
        for(int i=n;i;i--)
        {
            int pos=query(a[i]);
            if(pos!=-1)
            {
                e[++ed].u=p[i].idx;
                e[ed].v=p[pos].idx;
                e[ed].len=abs(p[pos].y-p[i].y)+abs(p[pos].x-p[i].x);
            }
            add(a[i],p[i].x+p[i].y,i);
        }
    }
    Kruskal();
}```