【luogu题解】P1546 最短网络 Agri-Net

2018-09-01 05:38:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  • 题目

  约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过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 }

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ2023: [Usaco2005 Nov]Ant Counting 数蚂蚁(dp)

下一篇:BZOJ1093: [ZJOI2007]最大半连通子图(tarjan dp)