HDU 1233 还是畅通工程(最小生成树)

Description:

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input:

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

Output:

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input:

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

Sample Output:

3
5

题目链接

Kruskal算法求最小生成树，Kruskal算法的思路是先按照每条边的权值由小到大进行排序然后从权值最小的边依次选择不构成回路的边。

判断是否构成回路的方式是使用并查集，推荐一篇不错的并查集详解博文

并查集详解

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;

struct connect {
    int u;
    int v;
    int dis;
}eg[maxn];

// Kruskal算法求最小生成树
int n,E,pre[maxn];

// 后面sort利用此bool函数对结构体信息按照边的权值升序进行排序
bool cmp(connect a,connect b) {
    return a.dis < b.dis;
}

// init函数将自身的上级初始化为自身
void init(int n) {
    for (int i = 0;i <= n;++i) {
        pre[i] = i;
    }
}

// 此函数寻找x的上级
int find(int x) {
    int r = x;
    while (pre[r] != r) {       // 如果r的上级不是它本身
        r = pre[r];             // 查找r的最高级
    }
    // 路径压缩
    int i = x,j;
    while (i != r) {
        j = pre[i];             // 在改变上级之前用临时变量j记录下它的值
        pre[i] = r;             // 把上级改为最高级
        i = j;
    }
    return r;
    // 无路径压缩
    /*if (pre[x] == x) { return x; // 如果x的上级是它自身，说明已找到最高级，返回 } else { return pre[x] = find(pre[x]); // 否则继续递归查找 }*/
}

// 将x的最高级归为y的最高级下级
void join(int x,int y) {        // 将x与y进行连接
    int xx = find(x);           // 找到x的最高级
    int yy = find(y);           // 找到y的最高级
    if (xx != yy) {             // 如果x和y的最上级不是同一个人
        pre[xx] = yy;           // 将x的最上级xx归并到y的下级之中
    }
}

// kruskal算法
int kruskal() {
    sort(eg, eg + E, cmp);      // 对结构体信息按照边的权值升序进行排序
    init(n);                    // 用init函数将n的上级全部设为本身
    int res = 0;
    for (int i = 0;i < E;++i) {         // 循环遍历
        connect e = eg[i];              // 将eg[i]结构体赋值给e
        if (find(e.u) != find(e.v)) {   // 如果e.u的最上级和e.v的最高级不相同,相连后便不能构成回路
            join(e.u, e.v);     // 将e.u和e.v的最高级合并
            res += e.dis;       // 将e.u和e.v的权值加入到结果中
        }
    }
    return res;                 // 返回最小生成树结果
}

int main() {
	// 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n,n) {
        E = n * (n - 1) / 2;        // 计算输入信息组数
        for (int i = 0;i  < E;++i) {
            cin >> eg[i].u >> eg[i].v >> eg[i].dis;     // 输入信息，eg[i].u与eg[i].v之间的权值为eg[i].dis
        }
        int ans = kruskal();        // 利用kruskal算法求最小生成树的权值之和
        cout << ans << endl;        // 输出最小生成树权值之和结果
    }
    return 0;
}

最小生成树的另一种算法Prim算法,Prim算法的思路为n个顶点必定选择n-1条边，按照顶点一次选择最小权值的边，从起点开始筛选所有和起点相连的边，选择权值最小的那个，此时已生成树为两个顶点一条边，筛选新添加那个顶点相连的所有边，看看是否可以更新顶点到已生成树的权值，然后再次从其它未添加到已生成树的顶点中筛选权值最小的那个，再次用新添加的点更新其它顶点到已生成树的权值，直到把n个顶点全部连接起来便得到最小生成树。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;     // 正无穷（可以用memset）
const int maxn = 110;

struct connect {
    int v;      // 连接顶点
    int dis;    // 权值
};

vector<connect> Adj[maxn];      // Adj数组存连接情况
int n,E,dis[maxn];              // dis存每个顶点到已生成树的权值
bool vis[maxn] = {0};           // vis保存每个顶点的访问情况
int res = 0;                    // 结果（最小生成树的权值之和）

// Prim算法求最小生成树，这里1为起始点
int Prim() {
    mem(dis, INF);              // 将所有顶点的权值初始化为正无穷
    mem(vis, 0);                // 将所有顶点的访问情况设为未标记
    dis[1] = 0;                 // 将起点的权值设置为0
    res = 0;                    // 最小生成树结果初始化为0
    for (int i = 1;i <= n;++i) { // 遍历所有顶点，保证结果没有未被访问的顶点
        int u = -1,min = INF;   // 用min筛选出dis中的最小值（即未被筛选过的顶点到已生成树的权值的最小值），用u记录此顶点
        for (int j = 1;j <= n;++j) {     // 筛选过程
            if (vis[j] == 0 && dis[j] < min) {  // 判断条件为1.未被筛选过，2.小
                u = j;              // 记录顶点
                min = dis[j];       // 记录最小权值
            }
        }
        vis[u] = 1;     // 将筛选出的此点标记
        res += min;     // 将此点到已生成树的最小权值加入到结果中
        // 已生成树已更新
        for (int j = 0;j < Adj[u].size();++j) {     //更新未被筛选过的顶点到新已生成树的权值
            int v = Adj[u][j].v;        // v变量记录顶点
            if (vis[v] == 0 && Adj[u][j].dis < dis[v]) {    // 判断条件为1.此定点未被筛选过，2.此顶点到新已生成树的距离可以更新之前此顶点到已生成树的距离
                dis[v] = Adj[u][j].dis;     // 更新此顶点到已生成树的距离
            }
        }
    }
    return res;     // 返回结果
}

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n,n) {
        int a,b,distance;
        E = n * (n - 1) / 2;
        while (E--) {
            cin >> a >> b >> distance;
            connect add;
            add.v = b;
            add.dis = distance;
            Adj[a].push_back(add);
            // 无向图反向添加一次
            add.v = a;
            Adj[b].push_back(add);
        }
        // 输出结果
        cout << Prim() << endl;
        // 清空容器
        for (int i = 1;i <= n;++i) {
            Adj[i].clear();
        }
    }
    return 0;
}