首页 > 代码库 > 并查集+Priority_Queu+Kruskal实现最小生成树
并查集+Priority_Queu+Kruskal实现最小生成树
#include<stdio.h>#include<queue>using namespace std;#define MAX 99999int father[MAX];struct Edge{ int a; int b; int dist; bool operator<(const Edge & e) const { if(dist>e.dist) return true; return false; }}edge[MAX];void init(int n){ for(int i=1;i<=n;i++) { father[i]=i; }}int find(int x){ while(x!=father[x]) { x=father[x]; } return x;}void merge(int a,int b){ int i=find(a); int j=find(b); if(i!=j) { father[i]=j; }}int main(){ int n,m; int a,b,d; Edge tmp; priority_queue<Edge> q; while(scanf("%d%d",&n,&m)!=EOF) { init(n); for(int i=0;i<m;i++) { scanf("%d%d%d",&tmp.a,&tmp.b,&tmp.dist); q.push(tmp); } int sum=0; while(!q.empty()) { tmp = q.top(); //printf("11%d %d %d\n",tmp.a,tmp.b,tmp.dist); int a=find(tmp.a); int b=find(tmp.b); if(a!=b) { merge(a,b); printf("%d %d\n",tmp.a,tmp.b); sum+=tmp.dist; } q.pop(); } printf("%d\n",sum); } getchar(); return 0;}
并查集+Priority_Queu+Kruskal实现最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。