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

05-11 18:26