POJ - 3241 Object Clustering (모 팀 알고리즘 / 맨 해 튼 최소 생 성 트 리)
3597 단어 데이터 구조 - 블록 과 모 팀 알고리즘
제목: n 개의 점 을 제시 하고, i 개의 점 의 좌 표 는 (xi, yi) 이 며, 이 n 개의 점 이 형 성 된 맨 해 튼 에서 가장 작은 생 성 나무의 k 대 변 을 구한다.
분석: 맨 해 튼 최소 생 성 트 리 템 플 릿 문제 (평면 맨 해 튼 최소 생 성 트 리 에 대한 상세 한 설명
참조 코드:
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1e4+10;
const int maxm = 2e3+10;
int n,k;
int tree[maxm],pos[maxm];
struct Point{
int x,y,id;
int xsy;
};
Point point[maxn],p[maxn];
struct Edge{
int u,v,w;
Edge(){}
Edge( int uu, int vv, int ww)
{
u = uu, v = vv, w = ww;
}
bool operator < ( const Edge &e)const
{
return w < e.w;
}
};
vector e;
int fa[maxn];
bool cmpx( Point p1, Point p2)
{
if( p1.x != p2.x)
return p1.x > p2.x;
return p1.y > p2.y;
}
bool cmpxsy( Point p1, Point p2)
{
return p1.xsy < p2.xsy;
}
int dist( Point p1, Point p2)
{
return abs(p1.x-p2.x)+abs(p1.y-p2.y);
}
inline int lowbit( int x)
{
return x&-x;
}
void add( int i, int val, int id)
{
while( i < maxm)
{
if( tree[i] > val)
{
tree[i] = val;
pos[i] = id;
}
i += lowbit(i);
}
}
int query( int i)
{
int id = -1, val = INF;
while( i > 0)
{
if( tree[i] < val)
{
val = tree[i];
id = pos[i];
}
i -= lowbit(i);
}
return id;
}
void Manhaton( int n)
{
for( int i = 0; i < n; i++)
point[i].xsy = point[i].x-point[i].y;
sort(point,point+n,cmpxsy);
int now = 0, pre = -INF;
for( int i = 0; i < n; i++)
{
if( pre != point[i].xsy)
{
now++;
pre = point[i].xsy;
}
point[i].xsy = now;
}
sort(point,point+n,cmpx);
for( int i = 1; i < maxm; i++)
tree[i] = INF, pos[i] = -1;
for( int i = 0; i < n; i++)
{
int u = point[i].id;
int v = query(point[i].xsy);
if( v != -1)
e.push_back(Edge(u,v,dist(p[u],p[v])));
add(point[i].xsy,point[i].x+point[i].y,u);
}
}
void BuildEdge( int n)
{
e.clear();
for( int cnt = 0; cnt < 4; cnt++)
{
for( int i = 0; i < n; i++)
point[i] = p[i];
for( int i = 0; i < n; i++)
{
if(cnt == 1)
swap(point[i].x,point[i].y);
else if( cnt == 2)
point[i].y = -point[i].y;
else if( cnt == 3)
{
swap(point[i].x,point[i].y);
point[i].y = -point[i].y;
}
}
Manhaton(n);
}
}
int find( int x)
{
if( x == fa[x])
return x;
return fa[x] = find(fa[x]);
}
int MST( int n, int k)
{
if( n <= k)
return 0;
for( int i = 0; i < n; i++)
fa[i] = i;
sort(e.begin(),e.end());
int sz = e.size();
for( int i = 0; i < sz; i++)
{
int u = find(e[i].u);
int v = find(e[i].v);
if( u == v)
continue;
fa[u] = v;
n--;
if( n == k)
return e[i].w;
}
}
int main()
{
while( ~scanf("%d%d",&n,&k))
{
for( int i = 0; i < n; i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].id = i;
}
BuildEdge(n);
printf("%d
",MST(n,k));
}
return 0;
}