Highways POJ-1751 最小生成树 Prim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Highways POJ-1751 最小生成树 Prim算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1761字,纯文字阅读大概需要3分钟。
内容图文
![Highways POJ-1751 最小生成树 Prim算法](/upload/InfoBanner/zyjiaocheng/709/39a861e15eac4740a155852e765fa159.jpg)
Highways POJ-1751 最小生成树 Prim算法
题意
有一个N个城市M条路的无向图,给你N个城市的坐标,然后现在该无向图已经有M条边了,问你还需要添加总长为多少的边能使得该无向图连通.输出需要添加边的两端点编号即可。
解题思路
这个可以使用最短路里面的Prim算法来实现,对于已经连接的城市,处理方式是令这两个城市之间的距离等于0即可。
prim算法可以实现我们具体的路径输出,Kruskal算法暂时还不大会。
代码实现
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3;
struct Node{
int x, y;
}node[maxn];
int mp[maxn][maxn];
int vis[maxn];
int dis[maxn];//这里的dis存储的是其他各个点,到最小生成树中任意一点的最小值。
int line[maxn];
int n, m, ans=0;
void init()
{
for(int i=1; i<=n; i++)
{
dis[i]=mp[i][1];//开始的时候任选1号顶点加入到生成树中。这里是其他点到1号顶点的距离。
line[i]=1; //默认没有加入到生成树的点距离生成树中最近距离的点是1;
vis[i]=0; //默认没有点加入到生成树中。
}
}
bool prim()
{
ans=0;
vis[1]=1;
for(int i=1; i<n; i++)
{
int tmp=inf, k;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dis[j]<tmp)
{
tmp=dis[j];
k=j;
}
}
if(tmp==inf) return false;//生成最小树失败,该图不是连通的。
vis[k]=1;
ans+=dis[k];
if(mp[k][line[k]]!=0)
{
printf("%d %d\n", k, line[k]); //输出需要链接的两个点
}
for(int j=1; j<=n; j++) //以新加入生成树的点作为中间点,看看能优化
{
if(!vis[j] && dis[j] > mp[j][k])
{
line[j]=k;
dis[j]=mp[j][k];
}
}
}
return true;
}
int main()
{
while(scanf("%d", &n)!=EOF)
{
for(int i=1; i<=n; i++)
{
scanf("%d%d", &node[i].x, &node[i].y);
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
int tmp=(node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y);
mp[i][j]=tmp;
mp[j][i]=tmp;
}
}
scanf("%d", &m);
int x, y;
for(int i=1; i<=m; i++)
{
scanf("%d%d", &x, &y);
mp[x][y]=mp[y][x]=0;
}
init();
prim();
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的Highways POJ-1751 最小生成树 Prim算法全部内容,希望文章能够帮你解决Highways POJ-1751 最小生成树 Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。