POJ 3241 Object Clustering 모 팀 알고리즘

2991 단어 데이터 구조
n - k 맨 해 튼 거리, 모 팀 알고리즘 누 드 문제
Object Clustering
Time Limit: 2000MS
 
Memory Limit: 131072K
Total Submissions: 1584
 
Accepted: 366
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
Source
POJ Monthly--2007.08.05, Li, Haoyuan
[Submit]   [Go Back]   [Status]   [Discuss] 
/* ***********************************************
Author        :CKboss
Created Time  :2014 12 20      00 27 00 
File Name     :POJ3241.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn=22000;
const int INF=0x3f3f3f3f;

int n,k;

struct Edge
{
	int u,v,w;
}edge[maxn<<2];
int tot;

bool cmp_E(Edge a,Edge b)
{
	return a.wval)
		{
			C[i]=val; D[i]=id;
		}
	}
}

void query(int id,int pos,int val)
{
	pos+=1000;
	int Fr=-1,ret=INF;
	for(int i=pos;i<4000;i+=lowbit(i))
	{
		if(ret>C[i])
		{
			ret=C[i]; Fr=D[i];
		}
	}
	if(Fr!=-1) edge[tot++]=(Edge){id,Fr,ret-val};
}

void gao()
{
	memset(C,63,sizeof(C));
	sort(pt,pt+n,cmp_P);
	for(int i=n-1;i>=0;i--)
	{
		int pos=pt[i].y-pt[i].x;
		int sum=pt[i].y+pt[i].x;
		int id=pt[i].id;
		query(id,pos,sum);
		update(id,pos,sum);
	}
}

int fa[maxn];

int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

bool merge(int a,int b)
{
	a=find(a); b=find(b);
	if(a==b) return false;
	fa[a]=b;
	return true;
}

int solve()
{
	if(n==k) return 0;

	tot=0;

	gao();

	for(int i=0;i
유 니 버 설 단 방향 링크 디자인 (2) - 인터페이스의 실현
scrapy (3): 참조 요청

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage