题解 | #还是畅通工程#

#include<iostream>
#include<string>

const int MAX = 100;
int n;
int cnt;
int a, b;

int Graph[MAX][MAX];
int m_Father[MAX];//每个集合的父节点，下标表示节点代号，数组值表示节点父节点代号
int m_Height[MAX];//记录每个集合高度，实现低树向高树合并

int Find(int x)
{
    if(x != m_Father[x])
    {
        m_Father[x] = Find(m_Father[x]);
    }
    return m_Father[x];
}

void Union(int x,int y)
{
    int x_father = Find(x);
    int y_father = Find(y);
    if(x_father != y_father)
    {
        if(m_Height[x_father] < m_Height[y_father])
        {
            m_Father[x_father] = y_father;
        }else if(m_Height[x_father] > m_Height[y_father])
        {
            m_Father[y_father] = x_father;
        }else{
            m_Father[y_father] = x_father;
            m_Height[x_father]++;
        }
    }
}
//可以利用定义结构体，然后初始排序优化时间，但需要改变初始存储结构
int FindMin()//找到最小值，同时将横纵下标赋值给全局变量a，b；
{
    int min = INT_MAX;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(min > Graph[i][j])
            {
                min = Graph[i][j];
                a=i;
                b=j;
            }
        }
    }
    Graph[a][b] = INT_MAX;
    return min;
}

void Initial()
{
    for(int i = 1; i <=n; i++)
        {
            for(int j = 1; j <=n; j++)
            {
                Graph[i][j] = 0;
            }
        }

        for(int i=1;i <=n;i++)
        {
            m_Father[i] = i;//初始时所有节点的父节点都是自己
            m_Height[i] = 0;//初始时每个集合的高度都为0
        }
}

int main()
{
    int A, B, distance;
    while (std::cin >> n)
    {
        if(n == 0) break;
        cnt = 0;
        int num = n*(n-1)/2;
        Initial();
        for(int i = 0;i < num;i++)
        {
            std::cin >> A >> B >> distance;
            Graph[A][B] = distance;
            Graph[B][A] = distance;
        }
        int min;
        for(int i = 0;i < num;i++)//使用kruskal算法，每次从不同的集合取一条边加入最小生成树中
        {
            min = FindMin();
            if(Find(a) != Find(b))
            {
                cnt += min;
                Union(a, b);
            }
        }
        std::cout << cnt << std::endl;
    }
    
}