問(wèn)題鏈接：CCF201412試題。

問(wèn)題描述：

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

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

  現(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個(gè)水渠所需要的費(fèi)用（注意不是所有麥田之間都可以建立水渠）。請(qǐng)問(wèn)灌溉所有麥田最少需要多少費(fèi)用來(lái)修建水渠。

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

程序說(shuō)明：本程序使用Kruskal算法實(shí)現(xiàn)。有關(guān)最小生成樹的問(wèn)題,使用克魯斯卡爾算法更具有優(yōu)勢(shì)，只需要對(duì)所有的邊進(jìn)行排序后處理一遍即可。程序中使用了并查集，用來(lái)判定加入一條邊后會(huì)不會(huì)產(chǎn)生循環(huán)。n個(gè)結(jié)點(diǎn)的圖，其最小生成樹應(yīng)該是n-1條邊，這個(gè)作為程序處理的結(jié)束條件。這個(gè)程序?qū)崿F(xiàn)Kruskal算法部分的邏輯和代碼都是否簡(jiǎn)潔易懂。程序中，圖采用邊列表的方式存儲(chǔ)，按邊的權(quán)從小到大順序放在優(yōu)先隊(duì)列中，省去了排序。

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

/* CCF201412-4 最優(yōu)灌溉 */#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;     // 優(yōu)先隊(duì)列，用于存儲(chǔ)邊列表    edge e;    // 輸入數(shù)據(jù)    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;        }    }    // 輸出結(jié)果    cout << ans << endl;    return 0;}/*測(cè)試數(shù)據(jù)與結(jié)果兩組：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*/