這兩天在做最小生成樹(shù)，用的一直是Kruskal，不知道用Prim能把代碼寫(xiě)的短點(diǎn)兒。。。
這是有些被催的一題，題中兩個(gè)衛(wèi)星連接的點(diǎn)之間可以理解為沒(méi)有長(zhǎng)度，偶錯(cuò)誤的將
衛(wèi)星個(gè)數(shù)S理解為
沒(méi)有長(zhǎng)度的邊的個(gè)數(shù)，忘記了它們之間是有1之差的。O_O
關(guān)于Kruskal，可以先參閱：
http://m.shnenglu.com/hoolee/archive/2012/08/04/186253.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN0 250000
#define LEN1 510
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, S, P;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &S, &P);
for(i = 0; i < P; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
int count = 0;
for(i = 0; i < P; i++)//make edges
for(j = i + 1; j < P; 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 < P; i++)
{
set[i].p = i;
set[i].d = 0;
}
int setnum = P;
double len = 0;
for(i = 0; i < count && setnum - S > 0; i++)
{
int fb = Belong(egs[i].f);
int tb = Belong(egs[i].t);
if(fb != tb)
{
setnum--;
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:21
小鼠標(biāo) 閱讀(293)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
圖論