杭电1233——还是通畅工程~简单最小生成树问题

这题，典型的最小生成树问题，可以用Kruskal算法来实现，配合着并查集来高效求解。

先将各边按权值进行从小到大排列。遍历一个各边便可求解，时间复杂度为O（|E|log|V|），其中E为边的个数，V为顶点数。

下面是AC代码，代码中有注释：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

class data                
{
public:
    int from, to, cost;    //起点、终点、权值
};
data con[5000];            //定义边的结构体数组
int n, m, par[105];
int finds(int x)           //并查集查找函数。
{
    if(x == par[x])
        return x;
    else
        return par[x] = finds(par[x]);
}
void unite(int x, int y)  //并查集合并函数
{
    x = finds(x);
    y = finds(y);
    if(x == y)
        return;
    if(x < y)
        par[y] = x;
    else
        par[x] = y;
}
int cmp(const data& a, const data& b)   //排序的方式
{
    return a.cost < b.cost;
}
int Kru()
{
    int ans = 0;
    for(int i = 0; i <= n; i++)         //初始化并查集
        par[i] = i;
    sort(con, con + m, cmp);            //排序
    for(int j = 0; j < m; j++)
    {
        if(finds(con[j].from) != finds(con[j].to))   //判断是否属于同一个并查集，不是，则可以进行合并，这样就不会产生圈
        {
            unite(con[j].from, con[j].to);           //进行合并
            ans += con[j].cost;                      //加上权值
        }
    }
    return ans;
}
int main()
{
//    freopen("data.txt", "r", stdin);
    while(scanf("%d", &n) != EOF && n)
    {
        m = n * (n - 1) / 2;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &con[i].from, &con[i].to, &con[i].cost);
        }
        int ans = Kru();
        cout << ans << endl;
    }
    return 0;
}

杭电1233——还是通畅工程~简单最小生成树问题

原文：http://blog.csdn.net/qq_25425023/article/details/45310159