这两天在做最小生成树，用的一直是Kruskal，不知道用Prim能把代码写的短点儿。。。
这是有些被催的一题，题中两个卫星连接的点之间可以理解为没有长度，偶错误的将
卫星个数S理解为
没有长度的边的个数，忘记了它们之间是有1之差的。O_O
关于Kruskal，可以先参阅：
http://www.cppblog.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
小鼠标 阅读(280)
评论(0) 编辑 收藏 引用 所属分类:
图论