描述
学校有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