题目描述
农夫约翰被选为他们镇的镇长!
他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。
约翰的农场的编号是1,其他农场的编号是 2∼n。
为了使花费最少,他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表,你必须找出能连接所有农场并使所用光纤最短的方案。
输入格式
第一行包含一个整数 n,表示农场个数。
接下来 n 行,每行包含 n 个整数,输入一个对角线上全是0的对称矩阵。
其中第 x+1 行 y 列的整数表示连接农场 x 和农场 y 所需要的光纤长度。
输出格式
输出一个整数,表示所需的最小光纤长度。
样例
输入样例:
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例:
28
算法1
(最小生成树) $O(n^2)$
用“kruskal” 求解:
时间复杂度
参考文献
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1111111;
const int M = 1000;
struct node{
int a,b,c;
}e[N << 1];
/*
在结构体中重载一下
就不用“sort(e+1,e+m+1,cmp)” 中的“cmp”的了
struct node{
int a,b,c;
bool operator < (const node &x)const
{
return x.c>c;
}
}e[N << 1];
*/
int n,m,fa[N],ans,cnt;
bool cmp(node x,node y)//边权比较
{
return x.c<y.c;
}
int find(int x) //并查集
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&e[++m].c),e[m].a = i,e[m].b = j; //输入
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++) fa[i]=i; //并查集基本操作
for(int i=1;i<=m;i++)
{
int x = find(e[i].a);
int y = find(e[i].b);
if(x == y) continue;
ans+=e[i].c;
fa[y] =x;
cnt++;
}
printf("%d",ans);
return 0;
}