Object Clustering POJ - 3241 曼哈頓最小生成樹

題目連結：https://cn.vjudge.net/problem/POJ-3241

題意：n個點，按照曼哈頓距離，形成k個集合後，使得每個集合任意兩點的距離小于等于x，求最小的x

題解：也就是最小生成樹中，第n-k小的邊。 曼哈頓最小生成樹思路講解：點選檢視

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
const int N=10010;
struct Point{
	int x,y;
	int y_x;
	int id;
	bool operator <(const Point &xx)const
	{
		if(x!=xx.x) return x<xx.x;
		else return y<xx.y;
	}
}p[N];
int n,k;
int b[N],len;
int sum[N],posid[N];
void update(int x,int d,int id)
{
	while(x)
	{
		if(d<sum[x])
		{
			sum[x]=d;
			posid[x]=id;
		}
		x-=lowbit(x); 
	}
}
int query(int x)
{
	int minn=INF,id=-1;
	while(x<=len)
	{
		if(sum[x]<minn)
		{
			minn=sum[x];
			id=posid[x];
		}
		x+=lowbit(x);
	}
	return id;
}
int dis(Point x,Point y)
{
	return abs(x.x-y.x)+abs(x.y-y.y);
}
struct edge{
	int u,v,d;
	bool operator <(const edge &x)const
	{
		return d<x.d;
	}
}e[N*4];
int tot;
void addedge(int x,int y,int d)
{
	tot++;
	e[tot].u=x;
	e[tot].v=y;
	e[tot].d=d;
}
int f[N];
int fath(int x)
{
	return x==f[x]?x:f[x]=fath(f[x]);
}
void init()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	tot=0;
}
int main()
{
	int ca=1;
	int pos,cnt;
	int x,y;
	scanf("%d%d",&n,&k);
		init();
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&p[i].x,&p[i].y);
			p[i].id=i;
		}
		
		for(int i=0;i<4;i++)
		{
			if(i==1||i==3)
			{
				for(int j=1;j<=n;j++)
					swap(p[j].x,p[j].y);
			}
			else if(i==2)
			{
				for(int j=1;j<=n;j++)
					p[j].x=-p[j].x;
			}
			for(int j=1;j<=n;j++)
			{
				p[j].y_x=p[j].y-p[j].x;
				b[j]=p[j].y_x;	
			}
				
			sort(b+1,b+1+n);
			len=unique(b+1,b+1+n)-(b+1);
			sort(p+1,p+1+n);
			for(int j=1;j<=len;j++)sum[j]=INF;
			for(int j=n;j>=1;j--)
			{
				pos=lower_bound(b+1,b+1+len,p[j].y_x)-b;
				cnt=query(pos);
				if(cnt!=-1) addedge(p[j].id,p[cnt].id,dis(p[j],p[cnt]));
				update(pos,p[j].x+p[j].y,j);
			}
		}
		sort(e+1,e+1+tot);
		cnt=0;
		k=n-k;
		for(int i=1;i<=tot;i++)
		{
			x=fath(e[i].u);
			y=fath(e[i].v);
			if(x==y) continue;
			f[x]=y;
			cnt++;
			if(cnt==k)
			{
				printf("%d\n",e[i].d);
				break;
			}
		}
	
	return 0;
}