Cod sursa(job #689857)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 24 februarie 2012 21:58:34
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <iomanip>
#include <math.h>
#define NMAx 4120
#define EPS 0.000000001
#define oo (1<<30)
#define min(a,b) ((a)<(b)?(a):(b))
#define pp(a) ((a)*(a))
#define dist(i,j) sqrt((pp(X[i]-X[j])+pp(Y[i]-Y[j])))
#define father(nod) (nod/2)
#define left(nod) (2*nod)
#define right(nod) (2*nod+1)
#define cmp(a,b) (APM[Heap[a]]+EPS<APM[Heap[b]])
using namespace std;

int vf,loc[NMAx],Heap[NMAx];
int n,m;
double X[NMAx],Y[NMAx];
double S,APM[NMAx]; 

void up(int nod) {
	
	while(nod>1&&cmp(nod,father(nod))) {
		swap(Heap[nod],Heap[father(nod)]);
		swap(loc[Heap[nod]],loc[Heap[father(nod)]]);
		nod=father(nod);
		}
	
}
void down(int nod) {
	
	int son;
	do {son=0;
		if(left(nod)<=vf) {
			son=left(nod);
			if(right(nod)<=vf&&cmp(right(nod),son))
				son=right(nod);
			if(cmp(nod,son))
				son=0;
			}
		if(son) {
			swap(Heap[nod],Heap[son]);
			swap(loc[Heap[nod]],loc[Heap[son]]);
			nod=son;
			}
	}while(son);
	
}
void init_APM() {
	
	int i,j;
	double e;
	
	//include_APM(0)
	for(i=n+1;i<=n+m;i++) {
		
		e=oo;
		for(j=1;j<=n;j++)
			e=min(e,dist(i,j));
		
		APM[i]=e;
		Heap[++vf]=i;
		loc[i]=vf;
		up(loc[i]);
		}
	
}
void include_APM(int nod) {
	
	int i;
	
	for(i=n+1;i<=n+m;i++)
		if(APM[i]>dist(nod,i)+EPS&&loc[i]) {
			APM[i]=dist(nod,i);
			up(loc[i]);
			}
	
}
int radacina_Heap() {
	
	int nod=Heap[1];
	Heap[1]=Heap[vf];
	loc[Heap[1]]=1;
	loc[nod]=0;
	down(1);
	return nod;
	
}
void citire() {
	
	ifstream in("retea2.in");
	in>>n>>m;
	
	for(int i=1;i<=n+m;i++)
		in>>X[i]>>Y[i];
	
	in.close();
	
}
int main() {
	
	int nod,i;
	citire();
	
	init_APM();
	
	for(i=1;i<=m;i++) {
		nod=radacina_Heap();
		S+=APM[nod];
		include_APM(nod);
		}
	
	ofstream out("retea2.out");
	out<<fixed<<setprecision(9)<<S<<'\n';
	out.close();
	
	return 0;
	
}