畅通工程之最低成本建设问题 (30分)

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。
输入格式:

输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N；随后的M行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到N）以及该道路改建的预算成本。
输出格式:

输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。
输入样例1:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例1:

12

输入样例2:

5 4
1 2 1
2 3 2
3 1 3
4 5 4

输出样例2:

Impossible

这道题显然是最小生成树,学过数

据结构的话肯定是学过的,主要问

题在于你还记得吗…

这道题我用的是克鲁斯卡尔算法,定义了一个结构体数组,用来把每一个边都存起来,同时被存放的还有两个顶点以及边权.因为克鲁斯卡尔算法是每次从最小的边权里拿出来一个,所以把结构体数组按照边权排序.最后只要新拿到的边的两个顶点不在同一个集合内,也就是未曾搭建公路以使这两个顶点联通,那么就通过并查集里的join()函数让两个点联通,同时让ans加上边权.如果最终答案并不能使得图联通,也没有关系,只需要判断是否所有顶点都在同意集合内即可.

说实话,我并查集和克鲁斯卡尔算法早已经忘了,不过好在有一个代码模板文档,里面不讲述算法如何使用,只给算法的实现代码,靠着这个文档,我竟然做出来了这道题.

//
// Created by TIGA_HUANG on 2020/9/24.
//

#include <iostream>
#include <algorithm>

using namespace std;

int pre[1010];               //存放第i个元素的父节点
int union_search(int root) {                  //查找根结点
    int son, tmp;
    son = root;
    while (root != pre[root])                 //寻找根结点
        root = pre[root];
    while (son != root) {                     //路径压缩
        tmp = pre[son];
        pre[son] = root;
        son = tmp;
    }

    return root;
}


void join(int root1, int root2) {        //判断是否连通，不连通就合并
    int x, y;
    x = union_search(root1);
    y = union_search(root2);
    if (x != y)                          //如果不连通，就把它们所在的连通分支合并
        pre[x] = y;
}

int N, M;
struct Edge {
    int a, b;
    int length;
} edge[3005];

bool operator<(Edge &x, Edge &y) {
    return x.length < y.length;
}

int ans;

void kruskal() {
    ans = 0;
    for (int i = 0; i < M; ++i) {
        if (union_search(edge[i].a) != union_search(edge[i].b)) {
            join(edge[i].a, edge[i].b);
            ans += edge[i].length;
        }
    }
}
void init() {
    for (int i = 0; i <= N; ++i) {
        pre[i] = i;
    }
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> edge[i].a >> edge[i].b >> edge[i].length;
    }
    sort(edge, edge + M);
    init();
    kruskal();
    bool flag = true;
    for (int i = 2; i <= N; ++i) {
        if (union_search(i - 1) != union_search(i)) {
            flag = false;
            break;
        }
    }
    if (flag) {
        cout << ans << '\n';
    } else {
        cout << "Impossible\n";
    }
    return 0;
}

这是我参考的代码模板文档,说是参考几乎就是把里面的代码来了个复制粘贴