描述
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
输入
第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
输出
一个整数，表示最小的连接费用。
样例输入
3
0 1 2
1 0 1
2 1 0
样例输出
2
提示
注：表示连接1和2，2和3，费用为2。
思路：最小生成树的特点是要求联通所有点的图的路径要是最小的，所以需要排序，我们将每一条边存进结构体，按权值从小到大排序，然后就可以按照并查集的找父节点find的方法来生成树
1.创建边的结构体，x,y,z分别代表x到y两点的权值为z，输入总共k条边
2.排序，按权值z从小到大
3.设定当前已连接结点sum=0，最小花费ans=0
4.设定1-n的结点父节点为自己f[i] = i
5.遍历k条边，寻找第i条边的结点的父节点fx,fy，如果fx！=fy，证明x和y是可以构成连接的
6.构成连接，让fy父节点设为fx，已连接结点数sum++，最小花费则是第i条边的权值
7.当已连接数sum==n时，最小生成树完成
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N = 10001;
4 struct node{
5 int x,y,z;//创建边的结构体，x,y,z分别代表x到y两点的权值为z
6 }a[N];
7 int f[N];
8 bool cmp(node a,node b)
9 {
10 return a.z<b.z;
11 }
12 int find(int x)
13 {
14 if(f[x]!=x)f[x] = find(f[x]);
15 return f[x];
16 }
17 int main()
18 {
19
20 int n,k = 0;cin>>n;
21 for(int i=1;i<=n;i++)
22 for(int j=1;j<=n;j++)
23 {
24 cin>>a[++k].z;
25 a[k].x = i;a[k].y = j;
26 }
27 sort(a+1,a+1+k,cmp);//排序，按权值z从小到大
28 int sum = 0,ans = 0;//当前已连接结点sum=0，最小花费ans=0
29 for(int i=1;i<=n;i++)f[i] = i;
30 for(int i=1;i<=k;i++)
31 {
32 int fx = find(a[i].x);
33 int fy = find(a[i].y);
34 if(fx!=fy)//证明x和y是可以构成连接的
35 {
36 f[fy] = fx;//让fy父节点设为fx
37 sum++;//已连接结点数sum++
38 ans+=a[i].z;//最小花费ans则是第i条边的权值
39 if(sum==n)break;//当已连接数sum==n时，最小生成树完成
40 }
41 }
42 cout<<ans;
43 return 0;
44 }
标签：结点,计算机,int,sum,最小,布线,TZOJ,5788,连接 From： https://www.cnblogs.com/jyssh/p/17218577.html