数据结构实验之图论九：最小生成树

我不是女神ヾ 2022-06-05 08:30 138阅读 0赞

数据结构实验之图论九：最小生成树  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
Problem Description

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

Input

输入包含多组数据，格式如下。  
第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)  
剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

Output

每组输出占一行，仅输出最小花费。  
Example Input

3 2  
1 2 1  
1 3 1  
1 0  
Example Output

2  
0  
Hint

Author

赵利强

#include <iostream>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    int const MAX = 10056;
    
    
    typedef struct
    {
        int u, v, c;
    } city;
    int sum;
    int num;
    
    int bin[MAX];
    
    int fd(int x)
    {
        if(x != bin[x])
            x = fd(bin[x]);
        return x;
    }
    
    int main()
    {
        int n, m;
        while(cin >> n >> m)
        {
            city arr[MAX], t;
            sum = 0;
            num = 0;
            for(int i = 1; i <= n; i++)
            {
                bin[i] = i;
            }
            for(int i = 0; i < m; i++)
            {
                cin >> arr[i].u >> arr[i].v >> arr[i].c;
            }
            for(int i = 0; i < m - 1; i++)
            {
                for(int j = i + 1; j < m; j++)
                {
                    if(arr[i].c > arr[j].c)
                    {
                        t = arr[i];
                        arr[i] = arr[j];
                        arr[j] = t;
                    }
                }
            }
            for(int i = 0; i < m; i++)
            {
                int x = fd(arr[i].u);
                int y = fd(arr[i].v);
                if(x != y)
                {
                    sum += arr[i].c;
                    bin[y] = arr[i].u;
                    num++;
                }
                if(num == n - 1)
                {
                    break;
                }
            }
            cout << sum << endl;
        }
        return 0;
    }