最小生成树

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

---

根据题目的描述，我们可以得知这是一道图论的题目，图为带权无向图，边上的权值即为题中描述的道路修建成本。

现在需要我们根据已有的图，求该图的最小（权值和最小）生成树。

这时候就需要引入解决问题的最小生成树算法了。

Prim算法思路

1. 首先读入所有的边，边的数据结构是一个结构体，主要包括：起点、终点、权值。
2. 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态，初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。
3. 将某一个结点加入生成树（改变状态标志），因为所有结点都是要加入树的，所以选取哪个结点无所谓。
4. 遍历边权值最小的边<u,v>，其中u为已经加入树中的结点，v为未加入树中的结点。将该边<u,v>加入树中（改变边<u,v>的状态和结点v的状态）。
5. 重复步骤4直到边的数目为N-1（无环图N-1条边已经连接了N个结点）。

Kruskal算法思路

该算法比Prim更好理解

1. 首先读入所有的边，边的数据结构同上，将边按照权值大小由小到大进行排序。使用数组记录边加入生成树的状态，使用另一个数组记录结点的加入状态。
2. 选取当前未加入生成树的权值最小边加入树。
3. 重复步骤2直至全部结点已加入树种，至此算法结束。

---

最后给出题目的AC代码

题目代码

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

typedef struct edge
{
    int b;
    int e;
    int distance;
} edge;

bool my_cmp(edge a, edge b)
{
    return a.distance < b.distance;
}

int main()
{
    int m, n;
    cin >> n >> m;
    vector<edge> my_map(m);
    vector<bool> node_state(n + 1, false);
    vector<bool> edge_state(m, false);
    int a, b, distance;
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> distance;
        edge temp;
        temp.b = a;
        temp.e = b;
        temp.distance = distance;
        my_map[i] = temp;
    }

    sort(my_map.begin(), my_map.end(), my_cmp);

    node_state[1] = true;
    int sum = 1;
    int sum_dis = 0;
    int flag = 0;
    while (sum != n)
    {
        flag = 0;
        for (int i = 0; i < my_map.size(); ++i)
        {
            if (edge_state[i] == false)
            {
                if ((node_state[my_map[i].b] | node_state[my_map[i].e]) && !(node_state[my_map[i].b] & node_state[my_map[i].e]))
                {
                    sum_dis += my_map[i].distance;
                    edge_state[i] = true;
                    node_state[my_map[i].b] = node_state[my_map[i].e] = true;
                    sum++;
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0)
            break;
    }
    if (sum != n)
        cout << -1 << endl;
    else
        cout << sum_dis << endl;
    return 0;
}