题意分析

有(N)个谷仓，(M)条谷仓之间的连接路线及每条路线的成本。需要选择一组连接，使得所有谷仓连通（形成树状结构，无环），并且连接的总成本最大。若无法使所有谷仓连通，则输出(-1)。

解题思路

采用贪心算法，类似于求最小生成树的 Kruskal 算法，只不过这里将边按成本从大到小排序，然后依次选取边，只要选取的边不会形成环就加入到生成树中，直到所有谷仓连通，此时得到的就是最大生成树。

分析

- 首先将所有边按成本从大到小排序，这样每次取边时都是当前成本最大的边。
  
- 使用并查集来判断选取的边是否会形成环，若两个端点属于不同的集合（即未连通），则可以选取这条边，将两个集合合并。
  
- 当选取的边数达到\(n - 1\)时（\(n\)为谷仓数量，树的边数为顶点数减\(1\)），说明所有谷仓已连通，得到最大生成树。若边数不足\(n - 1\)，则无法连通所有谷仓。

实现步骤：

- 读取谷仓数量\(n\)和连接路线数量\(m\)。

- 初始化并查集的父节点数组\(p\)，将每个谷仓的父节点设为\(-1\)，表示每个谷仓都是独立的集合。

- 读取每条连接路线的信息，存入结构体数组\(a\)中。

- 对边按成本从大到小排序。

- 遍历排序后的边数组，对每条边判断其两个端点是否属于不同集合：

    - 若不同，则将边加入生成树（合并两个集合），并累加边的成本到\(ans\)中，同时边数\(cnt\)加\(1\)。
    
- 检查边数\(cnt\)是否等于\(n - 1\)，若不等于则将\(ans\)设为\(-1\)。
- 输出\(ans\)。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 20100;
struct Node
{
    int from;
    int to;
    int c;
    bool operator < (const Node &a)const
    {
        return c > a.c;
    }
}a[maxn];
int n, m, p[maxn];
int find(int x)
{
    if(p[x] == -1)
        return x;
    return p[x] = find(p[x]);
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(p, -1, sizeof(p));
        for(int i = 0; i < m; i++)
            scanf("%d%d%d", &a[i].from, &a[i].to, &a[i].c);
        sort(a, a + m);
        int ans = 0, cnt = 0;
        for(int i = 0; i < m; i++)
        {
            int x = find(a[i].from);
            int y = find(a[i].to);
            if(x != y)
            {
                cnt++;
                p[x] = y;
                ans += a[i].c;
            }
        }
        if(cnt != n - 1)
            ans = -1;
        printf("%d\n", ans);
    }    
    return 0;
}

代码说明：

1.定义结构体(Node)来存储边的信息，包括起点(from)、终点(to)和成本(c)，并重载小于号用于按成本从大到小排序。

2.find函数用于查找并查集中某个元素的根节点，路径压缩优化查找过程。

3.在主函数中，通过while循环读取输入数据，对边进行排序、并查集操作等实现最大生成树的求解，最终根据结果输出相应的值。