資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告