最小生成树算法(Prim算法)

1、最小生成树算法（Prim算法）畅通工程再续Problem Description相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。Input输入包括多组数据。输入首先包括一个整数T(T <= 20

2、0)，代表有T组数据。每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。 Output每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”. Sample Input2210 1020 2031 12 21000 1000 Sample Output1414.2oh!#include <stdio.h>#include <math.h>#define MAX 0x7

3、fffffff /定义无穷大，32位整数内 #define N 100 /定义最大点数 typedef struct /点坐标 int x,y; Point;Point pN+1; /保存各点坐标值 double mapN+1N+1; /各点之间的关系，用边权值表示 double distance(Point p1, Point p2)/求两点之间的距离 return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);double prim(int n, double cN+1N+1) /Prim算法，求n个点相连通的最小生成树，返回连通n

4、个点的最小代价和 double min,lowcostN+1,sum; int i,j,k,closestN+1,sN+1; s1=1; /从第一个点出发寻找连通点，构造最小生成树 sum=0; /初始代价和为0 for (i=2; i<=n; i+) /将其余n-1个点初始化 lowcosti=c1i; /lowcost是各点到当前连通树上的最小代价 closesti=1; /closet是各点离当前连通树上最近的点编号 si=0; /s用于标记各点是否已经被加入到连通树中 for (i=1; i<n; i+) /一共需要找n-1个点，因此需要n-1次循环 min=MAX; j=

5、1; for (k=2; k<=n; k+)/寻找距当前连通树代价最小的可达点，并将其加入连通树 if (lowcostk<min && !sk)/如果点可达且代价最小且其不在连通树中 min=lowcostk; j=k; if(min<MAX) sj=1; /将距当前连通树代价最小的可达点加入连通树 sum+=min; /如果一次循环中找到的最小代价为无穷大,说明该次循环找不到可达点,函数返回MAX else return MAX; /sj=1; for (k=2; k<=n; k+) /修改各点距当前最小连通树的相关值 if (cjk<lowc

6、ostk && !sk) lowcostk=cjk; closestk=j; return sum; /所有n个点都连通，返回最小代价和int main() int T,C,i,j; double d,r; scanf("%d", &T); while (T-) scanf("%d", &C); for (i=1; i<=C; i+) scanf("%d%d", &pi.x,&pi.y);/读入各点坐标值 /memset(map,0,sizeof(map); /此子句可有可无 for (i=1; i<C; i+) for (j=i+1; j<=C; j+) /无向图初始化 d = distance(pi,pj); if (d>=10 && d<=1000) /符合条件的两点之间边标上代价为权 mapij=mapji=100.0*d; /不符合条件的两点之间边权直接标为无穷大 else mapij=mapji=MAX; r=prim(C,map); if (r<MAX) printf("%.1lfn