hdu 1162 Eddy's picture（基础最小生成树）

本文主要是介绍hdu 1162 Eddy's picture（基础最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

        连接：点击打开链接

题意：

        n个点，是每个点相互连通（直接间接），求最短距离。

思路：

        prim（）最小生成树。把点的距离存在map中。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAXN 110
#define MAX 100000000struct node{double x,y;
}p[MAXN];double map[MAXN][MAXN];
double low[MAXN];
int vis[MAXN];
int n;void prim()
{int pos;double minn;double result = 0;memset(vis,0,sizeof(vis));pos = 1;vis[pos] = 1;for(int i=1; i<=n; i++){if(i != pos)low[i] = map[pos][i];}for(int i=1; i<n; i++){minn = MAX;for(int j=1; j<=n; j++){if(!vis[j] && minn > low[j]){minn = low[j];pos = j;}}result += minn;vis[pos] = 1;for(int j=1; j<=n; j++){if(!vis[j] && map[pos][j] < low[j])low[j] = map[pos][j];}}printf("%.2lf\n",result);
}int main()
{//freopen("input.txt","r",stdin);while(scanf("%d",&n) != EOF){for(int i=1; i<=n; i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)map[i][j] = sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y));}prim();}return 0;
}

-----------------------------------------------------------------------------------

战斗，永不停歇~~~~~~~~~~~~~~~~~~~~~

这篇关于hdu 1162 Eddy's picture（基础最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---