http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=914最小生成树prim算法。
最近刚学过Dijkstra的最短路算法，仔细分析一下，Dijkstra与Prim算法十分相似，区别在于更新点时的标准不同。前者是该点到起点的距离（用dist[]记录）最小，则将该点加入s，并更新相应的dist[]，后者是该点到s中任意一点的距离（用lowcost[]记录）最小，则将该点加入s，并更新相应的lowcost[]。
说来惭愧，这一题错在了格式上，没有认真读题，多保留了一位小数。
经验总结：认真读题。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define LEN 510
#define MAX 1000000.0
typedef struct
{
double x;
double y;
}Point;
Point point[LEN];
int P;
double C[LEN][LEN];
double Dis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void MakeEdges()
{
int i, j;
for(i = 0; i < P - 1; i++)
for(j = i + 1; j < P; j++)
{
C[i][j] = C[j][i] = Dis(point[i], point[j]);
}
}
double usedLine[LEN];
void Prim()
{
double lowcost[P];
int i, j, k;
int set[P];
// init
for(i = 0; i < P; i++)// init
{
lowcost[i] = C[0][i];
set[i] = 0;
}
set[0] = 1;
for(i = 0; i < P - 1; i++)
{
double min = MAX;
j = 0;
for(k = 1; k < P; k++)
{
if(lowcost[k] < min && set[k] == 0)
{
min = lowcost[k];
j = k;
}
}
set[j] = 1;
usedLine[i] = min;
for(k = 1; k < P; k++)
{
if(set[k] == 0 && C[j][k] < lowcost[k])
{
lowcost[k] = C[j][k];
}
}
}
}
int cmp(const void *a, const void *b)
{
double *a0 = (double*)a;
double *b0 = (double*)b;
if(*a0 > *b0)
return -1;
else
return 1;
}
int main()
{
int i, j, k;
int N, S;
scanf("%d", &N);
for(k = 0; k < N; k++)
{
scanf("%d%d", &S, &P);
for(j = 0; j < P; j++)
{
scanf("%lf%lf", &point[j].x, &point[j].y);
}
for(i = 0; i < P; i++)
for(j = 0; j < P; j++)
C[i][j] = MAX;
MakeEdges();
Prim();
qsort(usedLine, P - 1, sizeof(double), cmp);
printf("%.2lf\n", usedLine[S - 1]);
}
}
posted on 2012-04-25 21:58
小鼠标 阅读(118)
评论(0) 编辑 收藏 引用 所属分类:
图论