Minimum Spanning Tree(最小生成樹) 模板

Minimum Spanning Tree 模板

我是使用Kruskal演算法。Prim演算法在這裡。這裡是另外一個Kruskal演算法。

理論是說：如果兩個MST之間有一條路徑e，使得花費為最小，那這條路徑必定是大MST的其中一條。複雜度是 O(E lg E)

實作細節：
(1)每一個小MST利用Disjoint Set來實作，Find跟Union加上一些小技巧，即可變成                        O( alpha(N) )。

(2)邊要記得先排序，必要的時候記得定義<運算子

模板題：
(1) IOICamp Judge 40
(2) http://poj.org/problem?id=1258
(3) http://zerojudge.tw/ShowProblem?problemid=a129
(4) UVA 11631 - Dark roads  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2678

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N=10002;
const int MAX_M=100002;

struct edg {
    int a,b,c;
} e[MAX_M];

struct DisjointSet {
    int p[MAX_N+1];
    int rank[MAX_N+1];
    void init(int n) {
        for (int i=1;n>=i;i++) {
            p[i]=i;
            rank[i]=1;
        }
    }
    int Find(int x) {
        return x==p[x]?x:(p[x]=Find(p[x]));
    }
    void Union(int x,int y) {
        if (rank[x]<rank[y]) {
            p[Find(x)] = Find(y);
        }
        else {
            p[Find(y)] = Find(x);
        }
    }
} djs;

bool operator <(const edg& e1, const edg& e2) {
    return e1.c < e2.c;
}

long long int Kruskal (int n,int m) { // name of the algorithm
    long long min_cost=0;
    djs.init(n);
    sort(e,e+m);
    int i,j; //i-->計次, j-->第幾條邊
    for (int i=0,j=0; i<n-1 && j<m; i++) {
        while (djs.Find(e[j].a) == djs.Find(e[j].b)) j++;  //判斷��否已經在同一個MST
        djs.Union(e[j].a,e[j].b);
        min_cost+=e[j].c;
        j++; 
    }
    return min_cost;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;m>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            e[x].a=i;
            e[x].b=j;
            e[x].c=k;
        }
        long long ans = Kruskal(n,m);
        printf("%lld\n",ans);
    }
}