首页 > 代码库 > 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;}