POJ 3241 Object Clustering (최소 생 성 트 리) 문제 풀이

2821 단어
제목: 최소 생 성 트 리 K 번 째 큰 변 권 값 구하 기
생각:
폭력 에 크 루스 칼 을 더 하면, 너무 많은 시간 을 초과 할 수 있다.여기에 하나의 알고리즘 을 사용 하여 유효 변 의 가입 을 줄인다.
변 권 치 는 점 간 맨 해 튼 거리 이 므 로 각 점 의 효과 적 인 추가 선택 은 그 와 가장 가 까 운 4 개의 상한 방향 점 이 어야 한다.Y - x 를 색인 으로 하 는 y + x 의 값 을 트 리 배열 로 유지 한 다음 에 이 배열 에 저 장 된 것 은 점 의 첫 번 째 상한 방향의 거리 가 가장 가 까 운 점 입 니 다.이렇게 해서 우 리 는 매번 (i, N) 이 구간 에 현재 보다 더 작은 거리 가 있 는 지 찾 습 니 다 (y - x 를 색인 으로 하기 때문에 I > i 는 I 라 는 점 이 i 의 첫 번 째 상한 방향 에 있 음 을 표시 합 니 다).마지막 으로 각 방향의 변 을 다 추가 한 후 Kruskal 알고리즘 으로 변 을 추가 하고 K 에 추가 하면 출력 가중치 입 니 다.
증명 하 다.
상세 하 게 해석 하 다
 
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
const int N = 10000+5;
const int INIT = 1061109567;
using namespace std;
int n,k,cnt,Id[N],v[N],f[N];//id v  id  ，v    y-x    y+x  
struct node{
	int x,y,id;
	friend bool operator < (node a,node b){
		return a.x == b.x? a.y < b.y : a.x < b.x;
	}
}p[N];
struct edge{
	int u,v,w;
	friend bool operator < (edge a,edge b) {
        return a.w < b.w;
    }
}e[N<<2];
int lowbit(int x){
	return x&(-x);
}
void query(int id,int pos,int val){
	pos += 1000;
	int u = -1,ret = INT_MAX;
	for(int i = pos;i < N;i += lowbit(i)){
		if(v[i] < ret && v[i] != INIT){	//         
			ret = v[i];
			u = Id[i];
		}
	}
	if(u != -1){	//          
		e[cnt].u = id;
		e[cnt].v = u;
		e[cnt++].w = ret - val;
	}
}
void update(int id,int pos,int val){	//id,y-x,y+x 
	pos += 1000; 
	for(int i = pos;i > 0;i -= lowbit(i)){
		if(val < v[i]){//      
			v[i] = val;
			Id[i] = id;
		}
	}
}
int find(int x){
	if(x == f[x]) return x;
	else return f[x] = find(f[x]);
}
void kruskal(){
	sort(e,e+cnt);
	for(int i = 0;i < N;i++) f[i] = i;
	int num = n;
	for(int i = 0;i < cnt;i++){
		int x = find(e[i].u);
		int y = find(e[i].v);
		if(x != y){
			f[x] = f[y];
			num--;
			if(num == k){
				printf("%d
",e[i].w);
				return;
			}
		}
	}
}
void addEdge(){
	memset(v,63,sizeof(v));	//v == 1061109567
	sort(p,p+n);
	for(int i = n-1;i >= 0;i--){
		int index = p[i].y - p[i].x;
		int val = p[i].y + p[i].x;
		query(p[i].id,index,val);
		update(p[i].id,index,val);
	}
}
int main(){
	cnt = 0;
	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;	
	}
	
	addEdge();
	
	for(int i = 0;i < n;i++) swap(p[i].x,p[i].y);
	addEdge();
	
	for(int i = 0;i < n;i++) p[i].y = -p[i].y;
	addEdge();
	
	for(int i = 0;i < n;i++) swap(p[i].x,p[i].y);
	addEdge();
	
	kruskal();
    return 0;
}

다음으로 전송:https://www.cnblogs.com/KirinSB/p/9408799.html
TIL 1 [11/28] - React 개념 정리
hdu 4008 트 리 dp 시간 스탬프 트 리 구조 에서 의 응용

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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