Problem 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 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 個點的坐標，以及一個數 k，這 n 個點之間的距離定義為彼此的曼哈頓距離，現在要將這些點連接起來，使得連接的權值最小，輸出第 k 大的邊

思路：本質是曼哈頓距離最小生成樹，求出生成樹后輸出第 k 大的邊即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 10000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct BIT{//樹狀數組int arr[N];int Id[N];void init(){memset(arr,INF,sizeof(arr));memset(Id,-1,sizeof(Id));}int lowbit(int k){return k&(-k);}void update(int pos,int val,int id){while(pos>0){if(arr[pos]>val){arr[pos]=val;Id[pos]=id;}pos-=lowbit(pos);}}int read(int pos,int m){int minval=INF;int ans=-1;while(pos<=m){if(minval>arr[pos]){minval=arr[pos];ans=Id[pos];}pos+=lowbit(pos);}return ans;} }B; struct POS{//區域int x,y;int id;bool operator<(const POS &rhs) const{if(x!=rhs.x)return x<rhs.x;return y<rhs.y;} }pos[N]; struct Edge{int x,y;int dis;bool operator<(const Edge &rhs)const {return dis<rhs.dis;} }edge[N<<2],resEdge[N<<2]; int edgeTot,resEdgeTot; int father[N]; void build(int n){//在R1區域中建邊sort(pos,pos+n);int a[N],b[N];for(int i=0;i<n;i++){a[i]=pos[i].y-pos[i].x;b[i]=pos[i].y-pos[i].x;}//離散化sort(b,b+n);int num=unique(b,b+n)-b;B.init();for(int i=n-1;i>=0;i--){int poss=lower_bound(b,b+num,a[i])-b+1;int ans=B.read(poss,num);if(ans!=-1){//建邊edge[edgeTot].x=pos[i].id;edge[edgeTot].y=pos[ans].id;edge[edgeTot].dis=abs(pos[i].x-pos[ans].x)+abs(pos[i].y-pos[ans].y);//曼哈頓距離edgeTot++;}B.update(poss,pos[i].x+pos[i].y,i);} } void manhattan(int n,int k) {for(int dir=0;dir<4;dir++){//左側四個區域if(dir==1||dir==3){//變換區域for(int i=0;i<n;i++)swap(pos[i].x,pos[i].y);}else if(dir==2){//變換區域for(int i=0;i<n;i++)pos[i].x=-pos[i].x;}build(n);//建邊} } int Find(int x) {return father[x]==x?x:Find(father[x]); } void kruskal(int n,int k){resEdgeTot=0;for(int i=0;i<=n;i++)father[i]=i;sort(edge,edge+edgeTot);int cnt=n-k;for(int i=0;i<edgeTot;i++) {int x=edge[i].x,y=edge[i].y;int fx=Find(x),fy=Find(y);if(fx!=fy) {cnt--;father[fx]=fy;resEdge[resEdgeTot].x=x;resEdge[resEdgeTot].y=y;resEdge[resEdgeTot].dis=edge[i].dis;resEdgeTot++;}}} int main(){int n,k;scanf("%d%d",&n,&k);edgeTot=0;resEdgeTot=0;for(int i=0;i<n;i++){scanf("%d%d",&pos[i].x,&pos[i].y);pos[i].id=i;}manhattan(n,k);kruskal(n,k);sort(resEdge,resEdge+resEdgeTot);printf("%d\n",resEdge[resEdgeTot-k].dis);return 0; }

?

總結

以上是生活随笔為你收集整理的Object Clustering（POJ-3214）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。