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
小鼠標 閱讀(127)
評論(0) 編輯 收藏 引用 所屬分類:
圖論