- 题目
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。
- 输入
第一行： 农场的个数，N（3<=N<=100）。
第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。
- 输出
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
- 思路
我是用并查集加上贪心过的这道题（ 本来题目就不是很难 ），其中值得注意的地方是由于输入的矩阵是关于对角线对称的，所以只用读入一半就好了。
实现代码
1 #include <cstdio> 2 #include <algorithm> 3 ?4 using namespace std; 5 ?6 const int maxn = 200002; 7 ?8 struct node { 9 ????int st, ed, v;10 };11 node a[maxn];12 13 int f[maxn];14 15 bool cmp ( node a, node b) {16 ????return a.v < b.v;17 }18 19 int find ( int k ) {20 ????if ( k == f[k] ) ???return k;21 ????else {22 ????????f[k] = find( f[k] );23 ????????return f[k];24 ????}25 }26 27 int main () {28 ????int n, index = 0;29 ????scanf ( "%d", &n );30 ????for ( int i = 1; i <= n; i ++ ) {31 ????????for ( int j = 1; j <= n; j ++ ) {32 ????????????int k;33 ????????????scanf ( "%d", &k );34 ????????????if ( j > i ) {35 ????????????????index ++;36 ????????????????a[index].st = i; a[index].ed = j; a[index].v = k; 37 ????????????} ??38 ????????}39 ????}40 ????for ( int i = 1; i <= n; i ++ ) ???f[i] = i;41 ????sort ( a + 1, a + index + 1, cmp );42 ????int ans = 0, p = 1;43 ????for ( int i = 1; i <= index; i ++ ) {44 ????????if ( find( a[i].st ) != find( a[i].ed ) ) {45 ????????????ans += a[i].v;46 ????????????f[find( a[i].st )] = a[i].ed;47 ????????????p ++;48 ????????????if ( p == n ) ???break; 49 ????????}50 ????}51 ????printf ( "%d", &ans );52 ????return 0;53 }
【luogu题解】P1546 最短网络 Agri-Net
原文地址：https://www.cnblogs.com/cTz2o7pN/p/9562749.html