数据结构实验之图论九：最小生成树

约定不等于承诺〃 2022-05-17 11:24 154阅读 0赞

如果想要让一个有n个点的图是连通图，那至少需要n-1条边，一个连通无向图且不含有回路那么他就是一个树，那么一个有n个点的图可以找到n-1条边保持它的连通性并且不含有回路，那么就找到了这个图的最小生成树；举个例子吧：

Problem Description

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

Input

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

Output

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

Sample Input

3 2
    1 2 1
    1 3 1
    1 0

Sample Output

2
    0

思路：首先我们要找n-1条边，并且边的权值越小越好，那么我们需要对给定的边进行排序，接下来就是更重要的，就是需要判断当前边的两个顶点是否已经连通，不处理的话会产生回路就不是最小生成树了，我们可以利用并查集来处理，ac代码如下：

#include<bits/stdc++.h>
    using namespace std;
    int f[5012345];
    struct sdut
    {
        int a,b,c;
    }tree[10010];
    bool cmp(sdut a,sdut b)
    {
        return a.c<b.c;
    }
    int fin(int x)
    {
        if(f[x]==x)
            return x;
        else
        {
            f[x]=fin(f[x]);
            return f[x];
        }
    }
    int Merge(int u,int v)
    {
        int t1,t2;
        t1=fin(u);
        t2=fin(v);
        if(t1!=t2)
        {
            f[t2]=t1;///左边原则；
            return 1;
        }
        else
        return 0;
    }
    int main()
    {
         int n,m;
         while(cin>>n>>m)
         {
             memset(f,0,sizeof(f));
             if(m==0)
                cout<<0<<endl;
             else
             {
                 for(int i=1;i<=n;i++)
                    f[i]=i;
                 for(int i=0;i<m;i++)
                    cin>>tree[i].a>>tree[i].b>>tree[i].c;
                 sort(tree,tree+m,cmp);///对边的权值进行升序处理；
                 int sum=0,ct=0;;
                 for(int i=0;i<m;i++)
                 {
                     if(Merge(tree[i].a,tree[i].b))///判断当前边的两个顶点是否已经连通；
                     {
                         ct++;
                         sum+=tree[i].c;
    
                     }
                     if(ct==n-1)
                        break;
                 }
                 cout<<sum<<endl;
             }
         }
    }