Object Clustering
| Time Limit: 2000MS | Memory Limit: 131072K | |
| Total Submissions: 2640 | Accepted: 806 |
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 Nobjects 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 dij ≤ 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
6 2
1 2
2 3
2 2
3 4
4 3
3 1
Sample Output
2
题目大意：
（在平面坐标第一象限）给你n个整点，A(x1,y1)和B(x2,y2)两点之间的距离定义为|x1-x2|+|y1-y2|，求最小生成树第k大边。
曼哈顿最小生成树经典题。
首先这道题条件给的不充分啊：点都在第一象限（不包括坐标轴），没有重（chong）点。
大致理一下思路：
首先，如果将点两两相连，边数是O（n^2）的。但并非所有的边都有用。网上有很多相关的证明，可以证得，只需对一二象限均分的四个部分分别求最近的点加边。
其次，怎么处理呢。先考虑y轴左偏45度的那一块。先对y-x离散化，再对x排序（排序函数要注意，因为要把边界算上）,这样每次查询y-x和x比当前点大的点中最小值就好了（用线段树）。这一块实现起来确实比较麻烦，详见代码。
再次，其余三个部分通过坐标变换就可以套用第一部分的处理方式了。(x,y)(y,x)(-y,x)(x,-y)。
最后，跑个kruskal就ok了。
#include<cstdio>
#include<algorithm>using namespace std;const int maxn=;
const int inf=;struct tdot
{
int x,y;
int num;//每个点的序号
int dis;//离散化后的值
};
tdot dot[maxn+];//x
int cmp1(tdot a,tdot b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}//y-x
int cmp2(tdot a,tdot b)
{
if(a.y-a.x==b.y-b.x)
return a.x<b.x;
return a.y-a.x<b.y-b.x;
}//离散化及预处理
void discrete(int n)
{
sort(dot+,dot+n+,cmp2);
for(int i=;i<=n;i++)
dot[i].dis=i;
sort(dot+,dot+n+,cmp1);
}struct ttree
{
int l,r;
int num;
int mmin;
};
ttree tree[maxn*+];void pushup(int x)
{
if(tree[x].l==tree[x].r)
return;
if(tree[x*].mmin<=tree[x*+].mmin)
tree[x].mmin=tree[x*].mmin,tree[x].num=tree[x*].num;
else
tree[x].mmin=tree[x*+].mmin,tree[x].num=tree[x*+].num;
}void build(int x,int l,int r)
{
tree[x].l=l;tree[x].r=r;
tree[x].mmin=inf;
tree[x].num=;
if(l<r)
{
int mid=(l+r)/;
build(x*,l,mid);
build(x*+,mid+,r);
}
}void modify(int x,int pos,int mmin,int num)
{
if(tree[x].l==tree[x].r)
tree[x].mmin=mmin,tree[x].num=num;
else
{
int mid=(tree[x].l+tree[x].r)/;
if(pos<=mid)
modify(x*,pos,mmin,num);
else
modify(x*+,pos,mmin,num);
pushup(x);
}
}struct tret
{
int mmin,num;
};tret query(int x,int l,int r)
{
tret ret;
ret.mmin=inf;ret.num=;
if(l<=tree[x].l&&r>=tree[x].r)
{
ret.mmin=tree[x].mmin;
ret.num=tree[x].num;
return ret;
}
int mid=(tree[x].l+tree[x].r)/;
if(l<=mid)
{
tret ret0=query(x*,l,r);
if(ret.mmin>ret0.mmin)
ret.mmin=ret0.mmin,ret.num=ret0.num;
}
if(r>mid)
{
tret ret0=query(x*+,l,r);
if(ret.mmin>ret0.mmin)
ret.mmin=ret0.mmin,ret.num=ret0.num;
}
return ret;
}struct tedge
{
int a,b;
int w;
};
tedge edge[maxn*+];
int cnt=;//加边
void addedge(int n)
{
build(,,n);
for(int i=n;i>=;i--)
{
tret ret=query(,dot[i].dis,n);
if(ret.num!=)
{
edge[cnt].a=dot[i].num;
edge[cnt].b=ret.num;
edge[cnt++].w=ret.mmin-dot[i].x-dot[i].y;
}
modify(,dot[i].dis,dot[i].x+dot[i].y,dot[i].num);
}
}//kruskal用比较函数
int cmp(tedge a,tedge b)
{
return a.w<b.w;
}int fa[maxn+];int father(int x)
{
if(fa[x]==x)
return x;
return fa[x]=father(fa[x]);
}int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d%d",&dot[i].x,&dot[i].y);
dot[i].num=i;
} discrete(n);
addedge(n); for(int i=;i<=n;i++)
swap(dot[i].x,dot[i].y);
discrete(n);
addedge(n); for(int i=;i<=n;i++)
dot[i].x*=-;
discrete(n);
addedge(n); for(int i=;i<=n;i++)
swap(dot[i].x,dot[i].y);
discrete(n);
addedge(n); //kruskal
for(int i=;i<=n;i++)
fa[i]=i;
sort(edge+,edge+cnt,cmp);
for(int i=,j=;i<cnt;i++)
{
int fx=father(edge[i].a);
int fy=father(edge[i].b);
if(fx!=fy)
{
fa[fx]=fy;
j++;
}
if(j==n-k)
{
printf("%d\n",edge[i].w);
break;
}
} return ;
}
PS:看别人的解题报告只是一种学习的途径。代码的实现还是要靠自己写。这两者的深度是大不相同的，有些东西只有在自己写代码的时候才能体会到。这道题前前后后写了三遍，终于过了，开心。
