1350:【例4-11】最短网络(agrinet)

简介: 1350:【例4-11】最短网络(agrinet)

1350:【例4-11】最短网络(agrinet)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。

【输入】

第一行:农场的个数,N(3≤N≤100)。

第二行..结尾:后来的行包含了一个N×N的矩阵,表示每个农场之间的距离。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在80个字符,因此,某些行会紧接着另一些行。当然,对角线将会是0,因为不会有线路从第i个农场到它本身。

【输出】

只有一个输出,其中包含连接到每个农场的光纤的最小长度。

【输入样例】

4

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

【输出样例】

28

1. // 示例代码  Kruskal算法
2. #include <iostream>
3. #include <cstring>
4. #include <cstdio>
5. #include <algorithm>
6. #include <queue>
7. using namespace std;
8. 
9. const int N = 10005; // 定义常量 N,表示数组大小
10. struct point {
11. int x, y, v; // 记录边的两个顶点和权值
12. } a[N];
13. int f[105]; // 并查集数组,用于判断两个结点是否在同一连通块中
14. int n, m, x, k, ans; // n:图的结点数量,m:图中所有边的数量,x:当前读入的边的权值,k:已选边的数量,ans:当前生成树的总权值
15. 
16. int father(int x) { // 并查集查找祖先节点的函数
17. if (f[x] == x) return x; // 如果该结点的父亲节点就是它自己,直接返回
18. return f[x] = father(f[x]); // 否则,递归查找祖先节点,并将递归过程中访问的结点都直接挂在祖先结点下面(路径压缩)
19. }
20. 
21. void unionn(int x, int y) { // 并查集合并连通块的函数
22.     x = father(x); y = father(y);
23. if (x != y) f[y] = x; // 如果两个连通块不在一个集合中,则将其中一个集合的祖先节点挂在另一个集合的祖先节点下面
24. }
25. 
26. bool cmp(const point &a, const point &b) { // 对结构体数组按边权值大小排序的比较函数,用于 Kruskal 算法
27. return a.v < b.v;
28. }
29. 
30. int main() {
31.     cin >> n;
32. for (int i = 1; i <= n; i++) { // 读入图的邻接矩阵
33. for (int j = 1; j <= n; j++) {
34.             cin >> x;
35. if (x) {
36.                 m++;
37.                 a[m].x = i;
38.                 a[m].y = j;
39.                 a[m].v = x;
40.             }
41.         }
42.     }
43. 
44. for (int i = 1; i <= n; i++) f[i] = i; // 初始化并查集数组
45. 
46. sort(a + 1, a + m + 1, cmp); // 对所有边按边权值从小到大排序
47. 
48. for (int i = 1; i <= m; i++) { // 枚举每条边
49. if (father(a[i].x) != father(a[i].y)) { // 如果边的两个端点不在同一个连通块中
50. unionn(a[i].x, a[i].y); // 合并这两个连通块
51.             ans += a[i].v; // 更新当前最小生成树的总权值
52.             k++; // 记录已选边的数量
53.         }
54. if (k == n - 1) break; // 如果已经选择了 n-1 条边,则最小生成树建立完毕,退出循环
55.     }
56. 
57.     cout << ans; // 输出最小生成树的总权值
58. return 0;
59. }


相关文章
|
7月前
leetcode-2045:到达目的地的第二短时间
leetcode-2045:到达目的地的第二短时间
96 0
|
索引
【Leetcode -1721.交换链表中的节点 -2058.找出临界点之间的最小和最大距离】
【Leetcode -1721.交换链表中的节点 -2058.找出临界点之间的最小和最大距离】
49 0
|
7月前
|
算法 测试技术 C++
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
|
6月前
|
算法 调度 C++
【调度算法】共享函数vs拥挤距离
【调度算法】共享函数vs拥挤距离
85 1
|
算法 调度 C++
【OSTEP】进程调度: 介绍 | Convoy护航效应 | 最短任务优先(SJF) | 最短完成时间优先(STCF) | 轮转 RR | 结合I/O
【OSTEP】进程调度: 介绍 | Convoy护航效应 | 最短任务优先(SJF) | 最短完成时间优先(STCF) | 轮转 RR | 结合I/O
169 0
|
6月前
|
运维
计算机网络——计算机网络的性能指标(下)-时延带宽积、往返时间、利用率、丢包率
计算机网络——计算机网络的性能指标(下)-时延带宽积、往返时间、利用率、丢包率
327 0
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目(二)
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
|
7月前
|
算法 测试技术 C#
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目(三)
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
|
7月前
|
人工智能 BI 测试技术
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目(一)
【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
|
7月前
|
机器学习/深度学习 算法 测试技术
【深度优先】【图论】【C++算法】2045. 到达目的地的第二短时间
【深度优先】【图论】【C++算法】2045. 到达目的地的第二短时间
下一篇
DataWorks