数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找连接每个笛卡尔坐标的最小成本
假设我们有一组二维笛卡尔坐标点 (x, y)。我们可以连接 (x0, y0) 和 (x1, y1)，其成本为 |x0 - x1| + |y0 - y1|。如果允许连接任意数量的点，则必须找到使每个点都通过路径连接所需的最小成本。
因此，如果输入类似于 points = [[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2, -3]]，
则输出将为 14，因为从 (0, 0) 到 (0, 2)、(0, -2)、(2, 0)、(-2, 0) 的成本分别为 2，总计为 8，而 (2, 3) 最接近 (0, 2)，成本为 |2+1| = 3，对于 (2, -3) 它最接近 (0, -2)，成本也为 3。因此总成本为 8 + 6 = 14。
为了解决这个问题，我们将遵循以下步骤：
- MAX := 无穷大
- 定义一个函数 interval()，它将接收 i、j 和点数组 p，
- 返回 |(p[i, x] - p[j, x]) + |p[i, y] - p[j, y]||
- 从主方法中执行以下操作：
- n := p 的大小
- 如果 n < 2，则：返回 0
- 定义一个名为 distance 的数组，包含 n 个槽，并填充为 MAX
- 定义一个大小为 n 的名为 visited 的数组
- distance[0] := 0
- 对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
- min_d := MAX
- node := 0
- 对于初始化 j := 0，当 j < n 时，更新（j 增加 1），执行：
- 如果 visited[j] 为假且 distance[j] < min_d，则：
- min_d := distance[j]
- node := j
- 如果 visited[j] 为假且 distance[j] < min_d，则：
- visited[node] := true
- cost := cost + distance[node]
- 对于初始化 j := 0，当 j < n 时，更新（j 增加 1），执行：
- 如果 visited[j] 为假，则：
- d := interval(node, j, p)
- distance[j] := distance[j] 和 d 的最小值
- 如果 visited[j] 为假，则：
- 返回 cost
示例
让我们看看下面的实现以更好地理解：
#include <iostream>
#include <vector>
#define MAX 99999
using namespace std;
int interval(int i, int j, vector<vector<int>>& p) {
return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}
int solve(vector<vector<int>>& p) {
int n = p.size(), cost = 0;
if (n < 2) return 0;
vector<int> distance(n, MAX);
vector<bool> visited(n);
distance[0] = 0;
for (int i = 0; i < n; i++) {
int min_d = MAX, node = 0;
for (int j = 0; j < n; j++) {
if (!visited[j] && distance[j] < min_d) {
min_d = distance[j];
node = j;
}
}
visited[node] = true;
cost += distance[node];
for (int j = 0; j < n; j++) {
if (!visited[j]) {
int d = interval(node, j, p);
distance[j] = min(distance[j], d);
}
}
}
return cost;
}
int main(){
vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}};
cout << solve(points);
}输入
{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}输出
14
更新于：2021年10月16日
197 次浏览
广告