本文主要是介绍hdoj 1875 畅通工程再续 【最小生成树】【prim算法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
昨天看了一下prim算法，原来只是抱着试试看的态度看一下，没想到居然看懂了，多谢
Veegin大大的详细解释，写的太好了。ZAN！！！
链接
http://www.cnblogs.com/Veegin/archive/2011/04/29/2032388.html
本题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1875
这道题其实就是将每条边的距离都存到map数组里面，然后用prim算法找最短路径就可以了，但是这道题有个小细节就是不满足大于等于10小于等于1000就不能建桥，所以要加一个判断语句。话不多说直接看代码：（有解释）
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXNUM 0x3f3f3f3f //极大地一个值，表示此路不通
typedef struct{
double x, y;
}str;
str s[105];
double map[105][105], low[105];
int vis[105], n;
double getdis(str a, str b) //得到两点间的距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double prim() //求最短路径
{
int pos, i, j;
double min, result = 0;
memset(vis, 0, sizeof(vis));
pos = 1;
vis[1] = 1;
for( i = 1; i <= n; i ++)
if(i!= pos) low[i] = map[pos][i];
for(i = 1; i < n; i ++){
min = MAXNUM;
for(j = 1; j <= n; j ++){
if(!vis[j]&&min > low[j]){
min = low[j];
pos = j;
}
}
if(min == MAXNUM) return -1; //表示一个岛到除它之外的任意一个岛的距离都不满足大于等于10小于等于1000 结束函数
else{
result += min;
vis[pos] = 1;
for(j = 1; j <= n; j ++){
if(!vis[j]&&low[j] > map[pos][j])
low[j] = map[pos][j];
}
}
}
return result;
}
int main()
{
int t, i, j;
scanf("%d", &t);
while(t --){
scanf("%d", &n);
for(i = 1; i <= n; i ++){
scanf("%lf%lf", &s[i].x, &s[i].y);
}
for(i = 1; i < n; i ++){
for(j = i+1; j <= n; j ++){
double temp = getdis(s[i], s[j]);
if(temp >=10&&temp <= 1000) //判断满不满足条件
map[i][j] = map[j][i] = temp*100;
else
map[i][j] = map[j][i] = MAXNUM;
}
}
double ans = prim();
if(ans < 0)
printf("oh!\n");
else
printf("%.1lf\n", ans); //忘了加换行了，粗心的要死
}
}
这篇关于hdoj 1875 畅通工程再续 【最小生成树】【prim算法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
