Wednesday, February 08, 2012

Normal Kurskal algorithm (Cordinate Given)

/***
    Normal Kurskal (Cordinate Given)
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Node_num 10004

struct S
{
int u,v,cost;
};
S a[Node_num];

int Set[Node_num],Rank[Node_num];
int Node,Edge;
double x[10003],y[10003];

void make_set(int x)
{
Set[x] = x;
Rank[x] = 0;
}

int find_set(int x)
{
if(x != Set[x])
{
Set[x] = find_set(Set[x]);
}
return Set[x];
}

void Union(int x,int y)
{
if(Rank[x] > Rank[y])
{
Set[y] = x;
}
else
{
Set[x] = y;
if(Rank[x] == Rank[y])
{
Rank[y]++;
}
}
return;
}

int comp_fun(const void *m,const void *n)
{
S *x,*y;
x=(S*)m;
y=(S*)n;
return ( x->cost - y->cost );
}

int main()
{
int  test,n,k,i,j,u_set,v_set,flag;
double sum,t1,t2;

scanf("%d",&test);
while(test--)
{
flag = 1;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf %lf",&x[i],&y[i]);
k=0;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{

a[k].u=i+1,a[k].v=j+1;
t1=x[i]-x[j],t2=y[i]-y[j];
a[k].cost = t1*t1 + t2*t2;
k++;

}
}

qsort(a,k,sizeof(S),comp_fun);

for(i=0;i<=n;i++)
{
make_set(i);
}

sum = 0.0;
for(i=0; i<k ;i++)
{
u_set=find_set(a[i].u);
v_set=find_set(a[i].v);
if(u_set!=v_set)
{
sum += sqrt(a[i].cost);
Union(u_set,v_set);
flag = 0;
}
}
printf("%.2lf\n",sum);
if(test)
printf("\n");
}
return 0;
}
/*
Input:
1

3
1.0 1.0
2.0 2.0
2.0 4.0
Output:
3.41
*/

No comments:

Post a Comment