問題鏈接：CCF201412試題。

問題描述：

  雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個麥田挖了一口很深的水井，所有的麥田都從這口井來引水灌溉。

  為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。

  現在雷雷知道哪些麥田之間可以建設水渠和建設每個水渠所需要的費用（注意不是所有麥田之間都可以建立水渠）。請問灌溉所有麥田最少需要多少費用來修建水渠。

問題分析：這是一個最小生成樹的為問題，解決的算法有Kruskal（克魯斯卡爾）算法和PRim（普里姆） 算法。

程序說明：本程序使用Kruskal算法實現。有關最小生成樹的問題,使用克魯斯卡爾算法更具有優勢，只需要對所有的邊進行排序后處理一遍即可。程序中使用了并查集，用來判定加入一條邊后會不會產生循環。n個結點的圖，其最小生成樹應該是n-1條邊，這個作為程序處理的結束條件。這個程序實現Kruskal算法部分的邏輯和代碼都是否簡潔易懂。程序中，圖采用邊列表的方式存儲，按邊的權從小到大順序放在優先隊列中，省去了排序。

提交后得100分的C++語言程序如下：

/* CCF201412-4 最優灌溉 */#include <iostream>#include <vector>#include <queue>using namespace std;// 并查集類class UF {private:    vector<int> v;public:    UF(int n) {        for(int i=0; i<=n; i++)            v.push_back(i);    }    int Find(int x) {        for(;;) {            if(v[x] != x)                x = v[x];            else                return x;        }    }    bool Union(int x, int y) {        x = Find(x);        y = Find(y);        if(x == y)            return false;        else {            v[x] = y;            return true;        }    }};struct edge {    int src, dest, cost;    bool Operator < (const edge& n) const {        return cost > n.cost;    }};int main(){    priority_queue<edge> q;     // 優先隊列，用于存儲邊列表    edge e;    // 輸入數據    int n, m;    cin >> n >> m;    for(int i=1; i<=m; i++) {        cin >> e.src >> e.dest >> e.cost;        q.push(e);    }    // Kruskal算法    UF uf(n);    int ans=0, count=0;    for(;;) {        e = q.top();        q.pop();        if(uf.Find(e.src) != uf.Find(e.dest)) {            uf.Union(e.src, e.dest);            ans += e.cost;            if(++count == n -1)                break;        }    }    // 輸出結果    cout << ans << endl;    return 0;}/*測試數據與結果兩組：6 101 2 31 3 11 4 62 3 52 5 33 4 53 5 63 6 44 6 25 6 6134 41 2 12 3 42 4 23 4 36*/