poj1258Agri-Net（最小生成树）

题目链接：http://poj.org/problem?id=1258

Description

Input

Output

Sample Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Sample Output

28

对于最小生成树，一般而言会有两种通用算法：
一：Kruskal算法：对边进行贪心操作（每条边一般而言会有三种属性值：val:边的权值、(x,y):边连接的两个点的编号）
　　1）将所有的边按照边的权值进行从小到大的排序（结构体类型的排序，三个属性值是一体的）；
　　2）设一棵树为T，将边从小到大进行遍历，若是加入这条边不会形成圈（形成圈了，则一定不是树，便一定权值和不是最小），就将这条边加入树T中，如此循环，
　　　 直到遍历完所有的边。最后便会生成一颗最小生成树。（至于如何判断假如一条边会不会形成圈，可以使用并查集的知识进行实现（若新加入的边的两个顶点
　　　 不在一个集合中，则不会形成圈））。
poj1258的Kruskal的AC代码：

#include<iostream> //利用最小生成树中的kruskal算法
#include<cstdio>
#include<algorithm>
using namespace std;
int bin[120];
struct node{
int val,x,y;
}a[10010];
int cmp(struct node a,struct node b){
return a.val<b.val;
}
int find(int x){
if(bin[x]==x) return x;
else return bin[x]=find(bin[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
bin[x]=y;
}
int main(){
int n,d;
struct node c;
while(cin>>n){
int k=0;
for(int i=1;i<=n;i++) //利用并查集的知识防止生成圈，若生成圈则一定不是最小
bin[i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&d);
if(j>i) a[k].val=d,a[k].x=i,a[k].y=j,k++;
}
sort(a,a+k,cmp); //对边的长度进行排序
int sum=0;
for(int i=0;i<k;i++){//对边从小到大进行遍历
if(find(bin[a[i].x])!=find(bin[a[i].y])) unite(bin[a[i].x],bin[a[i].y]),sum+=a[i].val; //若不会生成圈，则放入集合
}
printf("%d\n",sum);
}
return 0;
}

poj1258Agri-Net（最小生成树）

原文：https://www.cnblogs.com/sunjianzhao/p/11442054.html