CCF201412-4 最优灌溉（解法二）（100分）

问题链接：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*/