Cod sursa(job #647262)

Utilizator balakraz94abcd efgh balakraz94 Data 11 decembrie 2011 12:57:50
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cmath>
#define infile "retea2.in"
#define outfile "retea2.out"
#define n_max 4005
#define INF 1<<30
#define pb push_back
#define mkp make_pair
#define FOR(g,it) \
   for(vector<int> ::iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;

struct punct
{ int x,y; } p[n_max];

struct muchie
{
	int A, B;
	double c;
} apm[2*n_max];

bitset < n_max > uz;
	
int dim_p, dim_apm ;	

int T[n_max], R[n_max];

int X, Y;

int N, M;

double  cost_apm;


inline double dist(punct A, punct B)
{ return sqrt( (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) ); }


int mycmp (const muchie &A, const muchie &B)
{ return A.c < B.c; }


int cauta (int x)
{
	int r,y;
	
	for(r=x; T[r]!=r; r=T[r]);
	
	while(T[x]!=x)
	{
		y = T[x];
		T[x] = r;
		x = y; 
	}
	
	return r;
}



void uneste(int x, int y)
{
	if(R[x] < R[y])
		T[x] = T[y];
	else
		T[y] = x;
	
	if(R[x] == R[y])
		R[x]++;
}




void kruskal()
{
	sort(apm+1, apm+dim_apm+1, mycmp);
	
	int nrm = 0, n = dim_apm;
	
	dim_apm = 0;
	
	for(int i=1;i<=n && nrm < dim_p - N; i++)
	{
		int m1 = cauta(apm[i].A);
		int m2 = cauta(apm[i].B);
		
		if(m1!=m2)
		{
			uneste(m1,m2);
			apm[++dim_apm] = apm[i];
			cost_apm += apm[i].c;
			nrm++;
		}
	}
	
}


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&N,&M);
	
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d", &X, &Y);
		
	    p[++dim_p].x = X;
		p[dim_p].y = Y;
	}
	
	T[1] = 1;
	R[1] = 1;
	
	for(int i=2;i<=N;i++)//UNESC CENTRALELE
	{
		T[i] = i;
		R[i] = i;
		uneste(i,1);
	}
	
	
	for(int i=N+1; i<=N+M;i++)
	{
		scanf("%d %d",&X, &Y);
		
		p[++dim_p].x = X;
		p[dim_p].y = Y;
		
		for(int j=1;j<dim_p;j++)
		{
			apm[++dim_apm].c = dist(p[dim_p],p[j]);
		    apm[dim_apm].A = j;
		    apm[dim_apm].B = dim_p;
		}
		
		T[dim_p] = dim_p;
	    R[dim_p] = 1;
	}	
	
	fclose(stdin);
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%.6f\n",cost_apm);
	
	fclose(stdout);
}


int main()
{
	citeste();

	kruskal();
	
	afiseaza();
	
	return 0;
}