1348:【例4-9】城市公交网建设问题

简介: 1348:【例4-9】城市公交网建设问题

1348:【例4-9】城市公交网建设问题

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

【题目描述】

有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?

【输入】

n(城市数,1<≤n≤100)

e(边数)

以下e行,每行3个数i,j,wij,表示在城市i,j之间修建高速公路的造价。

【输出】

n-1行,每行为两个城市的序号,表明这两个城市间建一条高速公路。

【输入样例】

5 8

1 2 2

2 5 9

5 4 7

4 1 10

1 3 12

4 3 6

5 3 3

2 3 8

【输出样例】

1  2

2  3

3  4

3  5

1. // 示例代码  Prim算法
2. #include <iostream>
3. #include <cstring>
4. #include <cstdio>
5. #include <algorithm>
6. #include <queue>
7. using namespace std;
8. 
9. const int N = 105; // 定义常量 N,表示数组大小
10. int n, e, x, y, w;
11. int g[N][N]; // 保存图的邻接矩阵
12. int ans[N]; // 记录当前最小生成树中每个点的父亲节点编号
13. bool v[N];   // 标记哪些点已经在MST中
14. 
15. struct nod {
16. int to, w;
17. bool operator < (const nod &other) const { // 重载小于号运算符,使得该结构体对象可被优先队列使用(小根堆)
18. return w > other.w;  // 按权值从小到大排序
19.     }
20. };
21. 
22. void prim() {
23.     priority_queue<nod> pq;
24.     pq.push({1, 0}); // 将结点 1 加入最小生成树中,其父亲节点为 0
25. 
26. while (!pq.empty()) {
27.         nod t = pq.top();
28.         pq.pop();
29. 
30. if (v[t.to]) continue; // 如果已经在最小生成树中,则忽略
31.         v[t.to] = true; // 标记该结点已加入MST
32. 
33. if (t.w != 0) { // 输出点与其父亲节点之间的边
34.             cout << ans[t.to] << " " << t.to << endl;
35.         }
36. 
37. for (int i = 1; i <= n; i++) { // 枚举所有未访问过的结点
38. if (!v[i] && g[t.to][i] < 0x3f3f3f3f) { // 如果可从 t.to 到达i,并且 i 未被访问过
39.                 pq.push({i, g[t.to][i]}); // 将 i 加入优先队列
40. if (g[t.to][i] < g[ans[i]][i]) ans[i] = t.to; // 更新当前最短距离
41.             }
42.         }
43.     }
44. }
45. 
46. int main() {
47.     cin >> n >> e;
48. memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为正无穷
49. for (int i = 1; i <= e; i++) {
50.         cin >> x >> y >> w;
51.         g[x][y] = g[y][x] = w; // 读入边信息,建立双向边
52.     }
53. for (int i = 1; i <= n; i++) ans[i] = i; // 最开始每个点的父亲节点都是自己
54. prim(); // 运行 Prim 算法求解最小生成树
55. return 0;
56. }


相关文章
|
4月前
|
传感器 监控 算法
|
传感器 自动驾驶 数据可视化
数字孪生与未来城市建设
数字孪生技术的引入是 21 世纪最具开创性的创新。如今,数字孪生技术已在各个经济领域得到直接应用,尤其是在制造、医疗保健等领域。
333 0
数字孪生与未来城市建设
|
城市大脑 安全 自动驾驶
智能城市 or 智慧城市 ?
城市是为人服务的,城市中的各种信息化、自动化、智能化技术也是以满足人们工作生活的安全、高效、舒适为目的的,只有智商没有情商的城市是让人无所适从的,就像评定职称时只看垃圾论文不看呕心专著一样得形忘意,实际上,智商+情商才是智慧,智慧能够解决智能解决不了的问题,比如塞翁失马、望梅止渴等。
智能城市 or 智慧城市 ?