题目描述

这题十分太平洋（这题十分水）

农夫约翰被选为他们镇的镇长！

他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。

约翰的农场的编号是1，其他农场的编号是 2∼n。

为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。

你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。

输入格式
第一行包含一个整数 n，表示农场个数。

接下来 n 行，每行包含 n 个整数，输入一个对角线上全是0的对称矩阵。
其中第 x+1 行 y 列的整数表示连接农场 x 和农场 y 所需要的光纤长度。

输出格式
输出一个整数，表示所需的最小光纤长度。

数据范围
3≤n≤100
每两个农场间的距离均是非负整数且不超过100000。

样例

输入样例：
4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

输出样例：
28

算法1

(Kruskal) $O(n^2)$

运用并查集和结构体，将最短路线排序，若他们不再一个集合，那么就合并且加上费用

时间复杂度

O(n^2)

参考文献

100%自己做

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct jgt
{
    int a,b,c;
}nm[10010];
int f[110];
int fa(int x)
{
    if(f[x]==x) return f[x];
    return f[x]=fa(f[x]);
}
bool cmp(jgt zma,jgt zmb)
{
    return zma.c<zmb.c;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>nm[(i-1)*n+j].c;
        nm[(i-1)*n+j].a=i;
        nm[(i-1)*n+j].b=j;
    }
    for(int i=1;i<=n;i++)
    f[i]=i;
    sort(nm+1,nm+n*n+1,cmp);
    int tzy;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            tzy=(i-1)*n+j;
            if(fa(nm[tzy].a)!=fa(nm[tzy].b))
            {
                ans=ans+nm[tzy].c;
                f[fa(nm[tzy].a)]=fa(nm[tzy].b);
            }
        }
    }
    cout<<ans;
    return 0;
}