时限：1000MS 内存限制：10000K
提交材料共计： 62643 接受： 25922
描述
农夫约翰被选为他的镇长！他的竞选承诺之一是将互联网连接到该地区的所有农场。他当然需要你的帮助。
农场主约翰为他的农场订购了一条高速连接，并将与其他农民分享他的连接。为了降低成本，他想要铺设最少的光纤来连接他的农场和所有其他农场。
给出连接每一对农场需要多少纤维的清单，你必须找到将它们连接在一起所需的最小纤维数量。每个农场必须连接到其他农场，以便一个包可以从任何一个农场流到任何其他农场。
两个农场之间的距离不超过100000。
输入包括几个案例。对于每一种情况，第一行包含农场的数量，n(3<=n<=100)。下面的行包含在矩阵，其中每个元素显示从农场到另一个农场的距离。从逻辑上讲，它们是n个空间分离整数的n行.。在物理上，它们的长度限制为80个字符，因此有些行继续在其他行上。当然，对角线是0，因为从农场i到它本身的距离对于这个问题并不有趣。
输出
对于每个情况，输出一个整数长度，这是连接整个农场集所需的最小纤维长度之和。
样本输入
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
样本输出
28
方法一、克鲁斯卡尔算法实现：
#include <iostream>
#include <cstdio>
#define NUM 105
using namespace std;
int N;//农场的数量
int Graph[NUM][NUM];
int K_r_Agri()
{
int totle_value = 0;
int set[NUM];
for(int i = 1;i<=N;i++)
set[i] = i;//初始化set数组
int k = 1;
int a = 1;
int b = 1;
int min_ = 1<<30;//找到最小的权值；(也就是最小的距离)
while(k<=N-1){
for(int i = 1;i<=N;i++)
for(int j = i+1;j<=N;j++)
if(Graph[i][j]<min_){
min_ = Graph[i][j];
a = i;
b = j;
}
int temp = min_;
min_ = Graph[a][b] = 1<<30;
if(set[a]!=set[b]){
totle_value+=temp;
k++;
int t = set[b];
for(int i = 1;i<=N;i++)
if(set[i]==t)
set[i] = set[a];
}
}
return totle_value;
}
int main()
{
while(~scanf("%d",&N)){
for(int i = 1;i<=N;i++)
for(int j = 1;j<=N;j++)
cin>>Graph[i][j];
cout <<K_r_Agri()<<endl;
}
return 0;
}
方法二：克鲁斯算法二：
#include <iostream>
#include <cstdio>
#define NUM 105
using namespace std;
int N,m;//农场的数量和边数
struct dot_line
{
int W;
int V;
int U;
}DL[NUM*NUM/2];//是一个结构体内东西：其中有 顶点坐标，两个定点之间的权值；
int xu_hao[NUM*NUM/2];//边的序号
int set[NUM];//表示nUM个顶点的是否都在哎统一集合中；（也就是入树）
int find(int x){
return set[x] == x? x: set[x] = find(set[x]);
}
int com(const int a,const int b){
return DL[a].W<DL[b].W;
}
int K_r_Agri()
{
int totle_value = 0;
for(int i=0;i<N;i++)
set[i] = i;
for(int i = 0;i<m;i++)
xu_hao[i] = i;
sort(xu_hao, xu_hao+m, com);//对边进行排序；
for(int i = 0;i<m;i++){
int e = xu_hao[i];
int a = find(DL[e].U);
int b = find(DL[e].V);
if(a!=b){
totle_value+=DL[e].W;
set[a] = b;
}
}
return totle_value;
}
int main()
{
while(~scanf("%d",&N)){
m = 0;
for(int i = 0;i<N;i++)
for(int j = 0;j<N;j++)
if(i<j){
DL[m].U = i;
DL[m].V = j;
cin>>DL[m].W;
m++;
}
else{
int k ;
cin>>k;
}
//
// for(int i = 0;i<m;i++)
// cout <<W[i]<<" ";
// cout <<endl;
cout <<K_r_Agri()<<endl;
}
return 0;
}
3、普利姆算法：
#include <iostream>
#include <cstdio>
#define NUM 105
using namespace std;
int N,m;//农场的数量和边数
int Graph[NUM][NUM];
struct set
{
int adj;//顶点号
int value;
}SET[NUM];
int min_xu()
{
int i = 1;
while(!SET[i].value&&i<=N)
i++;
int k = i;
int min = 1<<30;
for(int i = 1;i<=N;i++)
if(SET[i].value>0&&SET[i].value<min)
{min = SET[i].value;k = i;}
return k;
}
int Prim()
{
int ans = 0;
for(int i = 1;i<=N;i++){
SET[i].adj = 1;
SET[i].value = Graph[1][i];
}
SET[1].value = 0;//入集合；
for(int i = 1;i<N;i++){
int k = min_xu();
ans+=SET[k].value;
SET[k].value = 0;
for(int i = 1;i<=N;i++)
if(SET[i].value>Graph[k][i]){
SET[i].adj = k;
SET[i].value = Graph[k][i];
}
}
return ans;
}
int main()
{
while(~scanf("%d",&N)){
for(int i = 1;i<=N;i++)
for(int j = 1;j<=N;j++){
scanf("%d",&Graph[i][j]);
if(Graph[i][j] == 0)
Graph[i][j] = 1<<30;
}
printf("%d\n",Prim());
}
return 0;
}