prim解决最小生成树问题
2024-08-31 05:06:26
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std; const int MAXV = ;//最大顶点数
const int INF = ; //n为顶点数
//MAXV为最大顶点数
int n,m;
double G[MAXV][MAXV];
double d[MAXV];// 顶点到集合S的最短距离
bool vis[MAXV] = {false};//标记数组,vis[i] == true表示已访问 double prim()
{
fill(d,d+MAXV,INF);
d[] = ;//只有0号顶点到集合s的距离为0,其他全为INF
double ans = ;//存放最小生成树的边权之和 //找n个点
for(int i=;i<n;i++)
{
int u = -,MIN = INF;//u使d[u]最小,MIN存放该最小的d[u] //每次找一个到集合距离最小的点
for(int j = ;j < n;j++)
{
if(vis[j] == false && d[j] < MIN)
{
u = j; MIN = d[j];
}
} if( u== - )
{
return -;
} //标记u为已访问
vis[u] = true; ans += d[u]; for(int v=;v < n;v++)
{
//如果v未访问,且u能到达v,并且以u为中转可以是v离集合更近
if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v])
{
d[v] = G[u][v] ;
}
}
} return ans;
} struct point
{
int x;
int y;
}; point p[MAXV]; double getDis(point &a,point &b)
{
return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
} int main()
{
cin >> n; for(int i=;i<n;i++)
{
cin >> p[i].x;
cin >> p[i].y;
}
//初始化图G
fill(G[],G[] + MAXV * MAXV,INF); for(int i=;i<m;i++)
{
cin >> p[i].x;
cin >> p[i].y;
} for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
G[i][j] = getDis(p[i],p[j]);
}
} double ans = prim(); printf("%.2f \n",ans);
return ;
}
最新文章
- opencv单目摄像机标定
- 安装 LuaSocket
- UIViewController启动过程
- Unity-Animator深入系列---StateMachineBehaviour状态机脚本学习
- UVALive 4043 Ants(二分图完美匹配)
- 1.6 OWIN集成
- POJ-1004-Finanical Management
- React实现局部刷新
- Flask 接入第三方云通讯平台时出现 {‘172001’:’网络错误’}
- Android Gradle Issue - Flutter / Dart
- sql 左右连接 on 之后的and 和where的区别
- Eureka微服务ID
- 判断B是不是A的子结构
- iOS8新特性(2)——UIPopoverController和UIPresentationController
- linux 编译PHP memcache扩展
- ethereum(以太坊)(十四)--Delete
- 关联容器 // append方法
- Openstack深入了解虚拟机
- Linux下Tomcat启动报 The BASEDIR environment variable is not defined
- Git 2016视频教程