這里不再贅述了，關于最小生成樹Kruskal算法可以參閱：
http://www.shnenglu.com/hoolee/archive/2012/08/04/186253.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN1 110
#define LEN0 10000
typedef struct
{
double x;
double y;
}Point;
typedef struct
{
int f;
int t;
double len;
}Edge;
typedef struct
{
int p;
int d;
}Set;
Set set[LEN1];
Point ps[LEN1];
Edge egs[LEN0];
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len > b0 -> len ? 1 : -1;
}
int Belong(int i)
{
while(set[i].p != i)
i = set[i].p;
return i;
}
int main()
{
int i, j;
int n;
int count = 0;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < n; i++)//make edges
for(j = i + 1; j < n; j++)
{
egs[count].f = i;
egs[count].t = j;
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
egs[count++].len = sqrt(dx * dx + dy * dy);
}
qsort(egs, count, sizeof(Edge), cmp);
for(i = 0; i < n; i++)
{
set[i].p = i;
set[i].d = 0;
}
double len = 0;
for(i = 0; i < count; i++)
{
int fb = Belong(egs[i].f);
int tb = Belong(egs[i].t);
if(fb != tb)
{
len += egs[i].len;
int df = set[fb].d;
int dt = set[tb].d;
if(df > dt)
set[tb].p = fb;
else if(df == dt)
{
set[tb].p = fb;
set[fb].d++;
}
else
set[fb].p = tb;
}
}
printf("%.2lf\n", len);
//system("pause");
}
posted on 2012-08-04 16:40
小鼠標 閱讀(141)
評論(0) 編輯 收藏 引用 所屬分類:
圖論