还是畅通工程 POJ-1233【最小生成树】_综合

题目链接：HDU-1233

[kuangbin带你飞]专题六最小生成树

题目描述：

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

思路

Prim算法：
不断寻找距离最小生成树最近的顶点，直到加入最小生成树的点数等于顶点数终止;
Kruskal算法：
从权值最小的边开始加，当顶点已经添加过则跳过，直到加入的边数等于顶点数-1终止；
##易错点
1.每次加入前确保加入的权值比之前加入的权值要小，否则不加入（防止重边）；
如第一次给出 1-2边的权值为3，然后某次加边操作说 1-2边权值为10，这时候我们保留第一次的权值（保留权值较小的那次）
2.使用克鲁斯卡尔算法要注意，当加入的边 = 顶点数-1 时可以直接返回最小生成树的权值，但一定要注意吗即使边！= 顶点数 - 1 也不一定是不连通的，当n = 1 时一定要返回 0，否则会wa的很惨！！！

代码:

Prim算法：

#include <bits/stdc++.h>
using namespace std;#define MAX 110
#define INF 0x3f3f3f3fint mat[MAX][MAX], vis[MAX], dist[MAX];void init(int n)
{
    for(int i = 1; i<=n; i++){
    for(int j = 1; j<=n; j++){
    mat[i][j] =INF;}dist[i] = INF;}
}void Union(int x, int y, int val)
{
    if(val < mat[x][y]){
    mat[x][y] = mat[y][x] = val;}
}int Prim(int n)
{
    int sum = 0, k;dist[1] = 0;for(int i = 0; i<n; i++){
    int min_vertex, min_dist = INF;for(int j = 1; j<=n; j++){
    if(!vis[j] && min_dist > dist[j]){
    min_dist = dist[j];min_vertex = j;}}vis[min_vertex] = 1;sum += min_dist;for(int j = 1; j<=n; j++){
    if(!vis[j] && mat[min_vertex][j] < dist[j]){
    dist[j] = mat[min_vertex][j];}}}return sum;
}int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;while(cin >> n, n){
    init(n);memset(vis, 0, sizeof(vis));int m = n * (n-1) / 2;for(int i = 0; i<m; i++){
    int x, y, val;cin >> x >> y >> val;Union(x, y, val);}cout << Prim(n) << endl;}return 0;
}

Kruskal算法：


#include <bits/stdc++.h>
using namespace std;#define MAX 110int pre[MAX];struct Node{
    int x, y, val;
}S[5050];bool cmp(const Node &a, const Node &b)
{
    return a.val < b.val;
}void init(int n)
{
    for(int i = 1; i<=n; i++)pre[i] = i;
}int Find(int x)
{
    return x == pre[x] ? x : pre[x] = Find(pre[x]);
}int Kruskal(int n, int m)
{
    sort(S+1, S+m+1, cmp);int sum = 0, ans = 0;for(int i = 1; i<=m; i++){
    int x = Find(S[i].x);int y = Find(S[i].y);if(x != y){
    pre[x] = y;sum += S[i].val;ans++;}if(ans == n-1)return sum;}return sum;
}int main()
{
    int n;while(cin >> n, n){
    init(n);int m = n * (n-1) / 2;for(int i = 1; i<=m; i++){
    cin >> S[i].x >> S[i].y >> S[i].val;}cout << Kruskal(n, m) << endl;}return 0;
}