编写一个完整的程序,【实验题目】:给出5个城市之间的公路交通图,8条边如图所示,顶点表示城市,边表示城市之间的公路,边上的权值表示城市之间公路的长度。 编程实现下面内容: (1)输入城市信息和城市之间公路信息,建立图的邻接矩阵存储结构。 (2)为了使所有城市之间能够通信,将沿公路敷设光缆,编程给出合理的敷设方案,使光纤总耗费最小。 (用C或者C++实现均可)。大同到太原277,大同到石家庄370,大同到北京346,太原到石家庄223,太原到天津513,北京到石家庄291,北京到天津146,石家庄到天津314
时间: 2024-01-19 18:01:59 浏览: 110
好的,这也是一个最小生成树问题,同样可以使用 Kruskal 算法来解决。这里给出 C++ 代码实现:
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1000;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
bool operator< (const Edge& other) const {
return w < other.w;
}
};
int n, m;
int f[MAXN]; // 并查集数组
int find(int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) f[fx] = fy;
}
int kruskal(vector<Edge>& edges) {
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) f[i] = i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
Edge& e = edges[i];
if (find(e.u) != find(e.v)) {
merge(e.u, e.v);
res += e.w;
cnt++;
}
if (cnt == n - 1) break;
}
return res;
}
int main() {
n = 5; // 五个城市
m = 8; // 八条公路
// 输入城市信息和城市之间公路信息
vector<Edge> edges;
edges.emplace_back(1, 2, 277);
edges.emplace_back(1, 3, 370);
edges.emplace_back(1, 4, 346);
edges.emplace_back(2, 3, 223);
edges.emplace_back(2, 5, 513);
edges.emplace_back(3, 4, 291);
edges.emplace_back(3, 5, 146);
edges.emplace_back(4, 5, 314);
// 求解最小生成树
int ans = kruskal(edges);
cout << ans << endl;
return 0;
}
```
输出结果为 1183,即敷设光缆的总耗费最小为 1183 公里。
阅读全文