c语言实现
时间: 2023-07-13 11:19:05 浏览: 55
以下是C语言实现的代码,使用了Prim算法求解最小生成树:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 10005
#define INF 1e9
struct Point {
int x, y;
} p[MAXN];
int cmp(const void *a, const void *b) {
struct Point *pa = (struct Point *)a;
struct Point *pb = (struct Point *)b;
if (pa->y != pb->y) return pa->y - pb->y;
return pa->x - pb->x;
}
double getDist(struct Point a, struct Point b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double prim(int n) {
int i, j;
double ans = 0;
double d[MAXN];
int vis[MAXN] = {0};
for (i = 0; i < n; i++) d[i] = INF;
d[0] = 0;
for (i = 0; i < n; i++) {
int u = -1;
for (j = 0; j < n; j++) {
if (!vis[j] && (u == -1 || d[j] < d[u])) u = j;
}
vis[u] = 1;
ans += d[u];
for (j = i + 1; j < n; j++) {
if (!vis[j]) {
double dist;
if (p[j].y == p[u].y) dist = fabs(p[j].x - p[u].x);
else dist = fmin(getDist(p[i], p[j]), getDist(p[u], p[j]));
d[j] = fmin(d[j], dist);
}
}
}
return ans;
}
int main() {
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y);
qsort(p, n, sizeof(struct Point), cmp);
printf("%.2lf\n", prim(n));
return 0;
}
```
可以先输入住宅楼的个数n,然后输入每个住宅楼的横纵坐标,最后输出各住宅楼到主道路之间的辅道路最小长度总和。
注意,在求距离时,如果两个住宅楼在同一条水平线上,则它们之间的距离为它们横坐标之差;否则,它们之间的距离为它们到原点(或其他某个点)的距离的最小值。