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