標題:
資料結構 404 城市景點(難)
[打印本頁]
作者:
may
時間:
7 天前 22:48
標題:
資料結構 404 城市景點(難)
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。
2. 設計說明：
(1) 城市中有 N 個景點（編號為 0 ~ N-1），與 M 條雙向通行的道路，且每一條道路連結兩個景點。
(2) 請撰寫一個程式，讓使用者輸入 M 條連接任兩景點道路資料，找出從景點編號 S 到景點編號 E 所有可能的路徑中，經過景點個數最多的一條路徑（每一條路徑不能重複經過相同景點）。
(3) 若景點個數最多的路徑超過一條，則取景點編號加總最大的路徑。
提示：請使用圖結構搜尋所有路徑。
3. 輸入輸出：
輸入說明
第 1 列：兩個正整數 N、M，其中 N 為景點個數、M 為道路個數。
第 2~M+1 列：每列皆有兩個自然數，為該條道路連接的兩景點編號，共 M 條。
第 M+2 列：兩個自然數 S、E，其中 S 為起始景點編號、E 為結束景點編號。
（所有自然數之間，皆以一個半形空白間隔）
輸出說明
經過景點個數最多的路徑景點編號，編號間以一個半形空白間隔。
（若景點數最多的路徑超過一條，則取景點編號加總最大的路徑）
範例輸入1
6 9
0 1
0 2
0 3
0 4
1 4
2 4
3 4
3 5
4 5
0 5
範例輸出1
0 2 4 3 5
範例輸入2
4 4
0 1
0 2
1 3
2 3
1 3
範例輸出2
1 0 2 3
作者:
may
時間:
7 天前 22:54
回復
1#
may
#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
//#include <numeric> // 用於 accumulate 計算數值總和
//#include <algorithm>
using namespace std;
vector<vector<int>> graph; // 存儲無向圖（鄰接表）
vector<int> bestPath; // 最佳路徑
int maxLength = 0; // 最長路徑長度
int maxSum = 0; // 景點編號加總最大值
// 深度優先搜尋（DFS）
void dfs(int node, int end, vector<int>& path, vector<bool>& visited) {
path.push_back(node); // 加入當前景點
visited[node] = true; // 標記該景點已拜訪
if (node == end) { // 抵達終點
int pathLength = path.size();
int pathSum = accumulate(path.begin(), path.end(), 0);
// 更新最佳路徑條件：
// 1. 若新路徑長度較長，則更新
// 2. 若長度相同但編號加總較大，也更新
if (pathLength > maxLength || (pathLength == maxLength && pathSum > maxSum)) {
maxLength = pathLength;
maxSum = pathSum;
bestPath = path;
}
} else { // 繼續探索其他鄰近景點
for (int neighbor : graph[node]) {
if (!visited[neighbor]) { // 確保不重複拜訪
dfs(neighbor, end, path, visited);
}
}
}
path.pop_back(); // 回溯：移除當前景點
visited[node] = false; // 取消標記
}
int main() {
int N, M;
cin >> N >> M;
graph.assign(N, vector<int>()); // 初始化鄰接表
// 讀取 M 條道路資訊
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u); // 雙向通行
}
int S, E;
cin >> S >> E;
vector<int> path; // 暫存路徑
vector<bool> visited(N, false); // 紀錄景點是否被拜訪
dfs(S, E, path, visited); // 執行 DFS
// 輸出最佳路徑
for (size_t i = 0; i < bestPath.size(); i++) {
cout << bestPath[i] << (i == bestPath.size() - 1 ? "\n" : " ");
}
return 0;
}
複製代碼
--------------------------------------------------
解題思路
建立圖的鄰接表
使用 vector<vector<int>> graph 來存儲無向圖的連結關係。
使用 DFS（深度優先搜尋）找出所有路徑
透過 DFS 遍歷所有從 S 到 E 的可能路徑，避免重複經過同一個景點。
遇到終點時，根據條件檢查是否更新最佳路徑。
選擇最佳路徑
記錄 最大景點數量 的路徑。
若有多條符合條件的路徑，選擇 景點編號加總較大 的。
測資
測試00
輸入
6 9
0 1
0 2
0 3
0 4
1 4
2 4
3 4
3 5
4 5
0 5
預期輸出
0 2 4 3 5
解釋
所有路徑長度最大為 5
0 → 1 → 4 → 3 → 5（景點總和 = 13）
0 → 2 → 4 → 3 → 5（景點總和 = 14）
選擇編號總和較大的路徑 0 2 4 3 5
測試01
輸入
4 4
0 1
0 2
1 3
2 3
1 3
預期輸出
1 0 2 3
解釋
所有路徑長度最大為 4
0 → 1 → 3 → 2（景點總和 = 6）
1 → 0 → 2 → 3（景點總和 = 6）
景點總和相同，但 1 0 2 3 字典序較大，所以選擇此路徑。
測試 02
輸入
5 5
0 1
1 2
2 3
3 4
0 4
0 4
預期輸出
0 1 2 3 4
解釋
最長路徑：0 → 1 → 2 → 3 → 4（長度 5）
唯一的最長路徑，直接輸出
測試 03
輸入
7 8
0 1
1 2
2 3
3 6
0 4
4 5
5 6
2 5
0 6
預期輸出
0 1 2 5 6
解釋
可能的最長路徑：
0 → 1 → 2 → 3 → 6（景點總和 = 12）
0 → 1 → 2 → 5 → 6（景點總和 = 14）
選擇景點總和較大的 0 1 2 5 6
測試04
輸入
8 10
0 1
1 2
2 3
3 7
0 4
4 5
5 6
6 7
2 6
1 5
0 7
預期輸出
0 1 5 6 7
解釋
可能的最長路徑：
0 → 1 → 2 → 3 → 7（景點總和 = 13）
0 → 1 → 5 → 6 → 7（景點總和 = 19）
選擇景點總和較大的 0 1 5 6 7
這 5 組測資涵蓋 基本測試、分岔選擇、最大景點加總比對 等情境，適用於完整測試程式的正確性。
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2
