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. }
