P1546 最短网络 Agri-Net

那么这个题是一道最小生成树的板子题

在此讲解kruskal克鲁斯卡尔方法；

原理：

并查集在这里被用到；

众所周知：树满足这样一个定理：如果图中有n个节点并且相联通，那么找出n-1条连接所有节点的边并且使连接成的图中没有环（走一圈又回到原先节点的路径），那么这个图一定是一棵树。

那么，我们写代码时只要满足以上条件并且使得找到的n-1条边总和最小，那么这棵树就是最小生成树啦！QWQ。

那么，我们将每个点都看成一个集合，每个集合的初始值为这个点的编号，保证每个集合的值都不相同，从邻接矩阵（原谅本超级蒟蒻不会链式前向星）中用二重循环找出权值最小的边，将这条边连接的两个点所在的集合搞成一个集合（并查集操作），将集合的统一数值设为第一个点（始点）的集合的值，即将这两个集合加入生成树中，再用判断这两个点的集合的值是不是相同（是不是一个环）来决定是否加入树就行了。。

（放松一下手指。）

最后在双重循环中加入最外层循环int k=1;k<=n-1;k++来找n-1条边，就 AC 了

安利两个英语单词：矩阵matrix，联通connected

上代码：

#include<cstdio>//matrix为矩阵

#include<iostream>

#include<algorithm>

using namespace std;

int n,matrix[][],connect[],i0,j0,sum=,t;//matrix为输入的数字矩阵，connect为每个点所属的连通图，sum为最小边权值之和
int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&matrix[i][j]);//以上4行为输入操作

    for(int i=;i<=n;i++)

        connect[i]=i;//连通图初始化

    for(int k=;k<n;k++)//n-1条边

    {

        int minn=;//倒也可以是2147483647

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(matrix[i][j]&&connect[i]!=connect[j]&&matrix[i][j]<minn)

                {

                    minn=matrix[i][j];

                    i0=i;j0=j;//存下这个边的始点和终点

                }

        sum+=minn;//加入权值之和

        t=connect[j0];

        for(int i=;i<=n;i++)

            if(connect[i]==t)connect[i]=connect[i0];//找到集合中的元素（因为不止有一个所以for），将第二个集合合并到第一个中成为一个大的

    }

    printf("%d",sum);//输出最小权值之和（题目中为最小费用）

    return ;

}

我这个不是标准的并查集查找方式，标准的请详见我的博客https://www.cnblogs.com/lbssxz/p/10753073.html

完。。结。。QAQ

最短网络

P1546 最短网络 Agri-Net题解（克鲁斯卡尔）

P1546 最短网络 Agri-Net