c++用图来实现现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。代码
时间: 2023-06-15 12:07:41 浏览: 47
这个问题可以使用最小生成树算法来解决,常用的算法有Prim算法和Kruskal算法。
我们可以将每个村落看作一个顶点,将有可能建设成标准公路的若干条道路看作边,边的权值为建设成标准公路的成本。然后使用最小生成树算法来求解每个村落都有公路连通所需要的最低成本。
以下是使用Prim算法的C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n; // 村落数量
int cost[MAXN][MAXN]; // 存储边的成本
int dist[MAXN]; // 存储每个村落到已选定的村落集合的最小距离
bool vis[MAXN]; // 存储每个村落是否已经加入到已选定的村落集合中
vector<int> prim() {
memset(vis, false, sizeof(vis));
memset(dist, INF, sizeof(dist));
vector<int> selected; // 存储已选定的村落集合
selected.push_back(1); // 假设1号村落是第一个选定的村落
vis[1] = true;
// 初始化dist数组
for (int i = 2; i <= n; i++) {
dist[i] = cost[1][i];
}
while (selected.size() < n) {
int minDist = INF;
int minDistV = 0;
// 选出距离已选定村落集合最近的村落
for (int i = 2; i <= n; i++) {
if (!vis[i] && dist[i] < minDist) {
minDist = dist[i];
minDistV = i;
}
}
// 将选定的村落加入已选定的村落集合中
selected.push_back(minDistV);
vis[minDistV] = true;
// 更新dist数组
for (int i = 2; i <= n; i++) {
if (!vis[i] && cost[minDistV][i] < dist[i]) {
dist[i] = cost[minDistV][i];
}
}
}
return selected;
}
int main() {
cin >> n;
// 读入边的成本
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> cost[i][j];
}
}
// 使用Prim算法求解最小生成树
vector<int> selected = prim();
// 计算总成本
int totalCost = 0;
for (int i = 1; i < selected.size(); i++) {
totalCost += cost[selected[i - 1]][selected[i]];
}
cout << totalCost << endl;
return 0;
}
```
其中,prim函数使用了贪心策略,每次选取距离已选定村落集合最近的村落加入已选定的村落集合中,然后更新dist数组。最终,将已选定的村落集合中的所有边的成本相加即为所求的最低成本。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)