首页 > 代码库 > Kruscal Template
Kruscal Template
Kruscal elimination :
很裸的Kruscal Template(求最小生成树中最长路,即最短路中最长路)
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <climits>#include <cstring>#include <algorithm>#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;const int MAX = 10500;int root[MAX],n,m,cnt;struct Edge{ int s,e; int value;}edge[MAX];bool cmp(Edge a, Edge b){ return a.value < b.value;}void init(){ for(int i = 1; i <= n; ++i) root[i] = i;}int find(int x){ return root[x] == x ? x : (root[x] = find(root[x]));}void merge(int a,int b){ if(a < b) root[b] = a; else root[a] = b;}void kruskal(){ int i,j; cnt = 0; for(i = 1; i <= m; ++i){ int a = find(edge[i].s); int b = find(edge[i].e); if(a != b){ merge(a,b); ++cnt; } if(cnt >= n-1){ printf("%d\n",edge[i].value); break; } }}int main(){ int i,j; while(scanf("%d%d",&n,&m) != EOF){ for(i = 1; i <= m; ++i) scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].value); sort(edge + 1, edge + 1 + m, cmp); init(); kruskal(); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。