数据结构实验之图论九：最小生成树（Prim/Kruskal）

Description

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

Input

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

Output

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

3 2 1 2 1 1 3 1 1 0

Output

2
0

//Prim #include<bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3fconst int N = 200;int mp[N][N]; int book[N];int Prim(int n) {int dist[N];int sum = 0;//最终花费for(int i = 1; i <= n; i++){dist[i] = mp[1][i];//dist数组表示从1这个点开始，到其余各点的权值}book[1] = 1;//1这个点在开始时加入最小生成树，不进入接下来的循环int minn, u;for(int i = 1; i < n; i++){minn = INF;u = 0;for(int j = 1; j <= n; j++){if(!book[j] && dist[j] < minn)//找到生成树的下一个点{minn = dist[j];u = j;}}book[u] = 1;sum += minn;for(int v = 1; v <= n; v++)//在加入u这个新点之后更新dist数组的值{if(!book[v] && dist[v] > mp[u][v]){dist[v] = mp[u][v];}}}return sum; } int main() {int n, m, u, v, len;while(cin >> n >> m){memset(book, 0, sizeof(book));memset(mp, INF, sizeof(mp));for(int i = 1; i <= n; i++){mp[i][i] = 0;}while(m--){cin >> u >> v >> len;if(len < mp[u][v])//这个非常重要mp[u][v] = mp[v][u] = len;}cout << Prim(n) << endl;} } //Kruskal #include<bits/stdc++.h>using namespace std;const int N = 110, M = 1e4 + 10; int Next[N];struct node {int u, v, len; } edge[M]; int cmp(node a, node b) {return a.len < b.len; }void init(int n)//并查集初始化 {for(int i = 1; i <= n; i++)Next[i] = i; } int find_root(int i)//查找根节点 {if(Next[i] == i)return Next[i];else{Next[i] = find_root(Next[i]);return Next[i];} } int merage(int u, int v) {int t1 = find_root(u), t2 = find_root(v);if(t1 != t2){Next[t1] = Next[t2];return 1;}elsereturn 0; } int main() {int n, m;while(cin >> n >> m){int sum = 0;init(n);for(int i = 1; i <= m; i++)cin >> edge[i].u >> edge[i].v >> edge[i].len;sort(edge + 1, edge + 1 + m, cmp);for(int i = 1; i <= m; i++){if(merage(edge[i].u, edge[i].v))sum += edge[i].len;}cout << sum << endl;}return 0; }

总结

以上是生活随笔为你收集整理的数据结构实验之图论九：最小生成树（Prim/Kruskal）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。