Prim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Prim算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1514字,纯文字阅读大概需要3分钟。
内容图文
![Prim算法](/upload/InfoBanner/zyjiaocheng/839/b9ad114785194692851d241655179b86.jpg)
内置类型pair
介绍
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
const int maxn=5e3+5, maxm=4e5+5;
int n, m, head[maxn], nxt[maxm], v[maxm], w[maxm], cnt, dis[maxn];
bool tag[maxn]; //标记点是否被加入MST
void add(int x, int y, int z) { cnt++, v[cnt]=y, w[cnt]=z, nxt[cnt]=head[x], head[x]=cnt; }
int prim(int s)
{
memset(dis, 0x7f, sizeof(dis)); //清空dis数组
priority_queue<pii, vector<pii>, greater<pii> > Q; //小根堆
int num=1, ans=0; //num统计加入MST的点的数量,ans为MST边权和
tag[s] = true;
for(int i=head[s]; i; i=nxt[i])
if(v[i]!=s) Q.push(make_pair(w[i], v[i])), dis[v[i]]=min(dis[v[i]], w[i]);
while(!Q.empty() && num!=n)
{
while(!Q.empty() && tag[Q.top().second]) Q.pop();//忽略已加入MST的点
if(Q.empty()) break;
int x=Q.top().second; //最小dis
tag[x]=true, ans+=Q.top().first, num++; //加入mst
Q.pop();
for(int i=head[x]; i; i = nxt[i]) //使用x松弛与当前MST相连点的dis值
if(!tag[v[i]] && dis[v[i]]>w[i]) Q.push(make_pair(w[i], v[i])), dis[v[i]]=w[i];
}
if (num!=n) return -1;
else return ans;
}
int main(void)
{
scanf("%d%d", &n, &m);
for(int i=1, x, y, z; i<=m; i++) //x, y, z放在for内定义可以省一行空间
scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z);
int ans=prim(1);
if(ans!=-1) printf("%d\n", ans);
else printf("orz\n");
return 0;
}
内容总结
以上是互联网集市为您收集整理的Prim算法全部内容,希望文章能够帮你解决Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。