Board logo

標題: 資料結構 403 選課App(難) [打印本頁]
作者: may    時間: 2025-3-28 22:40     標題: 資料結構 403 選課App(難)

資料結構 403 選課App
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。
[attach]20841[/attach]
[attach]20838[/attach]
[attach]20840[/attach]
範例輸入1
3 2 4
1 2 3
1 3 2
範例輸出1
0
範例輸入2
6 4 6
4 2 10
3 6 3
5 3 8
2 3 6
1 6 4
範例輸出2
3
作者: may    時間: 2025-4-8 11:43

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <algorithm>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  7. const int MAXN = 105;
  8. vector<pair<int, int>> graph[MAXN]; // 存圖：{鄰接點, 權重}
  9. bool visited[MAXN];
  10. int countResult = 0;
  11. int Q;

  13. void dfs(int current, int minWeight) {
  14.     visited[current] = true;
  15.     if (minWeight >= Q) countResult++;

  17.     for (auto &neighbor : graph[current]) {
  18.         int next = neighbor.first;
  19.         int weight = neighbor.second;
  20.         if (!visited[next]) {
  21.             dfs(next, min(minWeight, weight));
  22.         }
  23.     }
  24. }

  26. int main() {
  27.     int N, k;
  28.     cin >> N >> k >> Q;

  30.     // 建圖
  31.     for (int i = 0; i < N - 1; ++i) {
  32.         int u, v, r;
  33.         cin >> u >> v >> r;
  34.         graph[u].push_back({v, r});
  35.         graph[v].push_back({u, r});
  36.     }

  38.     // 初始化 visited 陣列
  39.     fill(visited, visited + MAXN, false);

  41.     // DFS 遍歷，從節點 k 開始，初始最小值設為無窮大
  42.     visited[k] = true;
  43.     for (auto &neighbor : graph[k]) {
  44.         int next = neighbor.first;
  45.         int weight = neighbor.second;
  46.         if (!visited[next]) {
  47.             dfs(next, weight);
  48.         }
  49.     }

  51.     // 輸出結果（不包含自己）
  52.     cout << countResult << endl;

  54.     return 0;
  55. }
複製代碼
回復 1# may
作者: may    時間: 2025-4-8 22:28     標題: 測資

回復 2# may
測資
測資 00（極小邊界）
輸入：
2 1 5
1 2 6

輸出：
1

說明：
只有兩門課，從 C1 出發，C2 的相關性為 6 ≥ Q=5，所以符合。
✅ 測資 01（沒有符合的課）
輸入：
4 1 10
1 2 3
2 3 4
3 4 2

輸出：
0

說明：
從 C1 出發，所有其他點路徑上的最小值都 < 10，不符合。
✅ 測資 02（所有課程都符合）

輸入：
5 3 1
3 1 5
1 2 4
3 4 6
4 5 3

輸出：
4

說明：
從 C3 出發，到每個節點路徑上的最小值皆 ≥ 1，符合的有 4 個課程（除了自己）。
✅ 測資 03（只有特定幾門課符合）
輸入：
6 2 5
1 2 7
2 3 6
3 4 4
4 5 3
5 6 2

輸出：
2

說明：
從 C2 出發：
- 到 C1：min=7 → ✅
- 到 C3：6 → ✅
- 到 C4：min{6,4} = 4 ❌
- 到 C5：min{6,4,3} = 3 ❌
- 到 C6：min{6,4,3,2} = 2 ❌  
→ 只有 C1, C3 符合
✅ 測資 04（分支多的樹）
輸入：
7 1 3
1 2 4
1 3 5
1 4 2
2 5 6
2 6 1
3 7 3

輸出：
4

說明：
從 C1 出發：
- C2：4 ✅
- C3：5 ✅
- C4：2 ❌
- C5：min(4,6)=4 ✅
- C6：min(4,1)=1 ❌
- C7：min(5,3)=3 ✅  
符合：C2, C3, C5, C7 → 共4個
作者: may    時間: 2025-4-8 22:29

回復 1# may
解題步驟：
建立圖的鄰接表。

透過 DFS 從 Ck 出發，對於每個節點，記錄從 Ck 到該節點路徑上的最小 Rij。

若該最小值大於等於 Q，則表示此課可以推薦。

最後統計符合條件的課程數量（不包括自己）
作者: may    時間: 2025-4-8 22:51     標題: 問題一:visited 是什麼？

回復 4# may
問題一:visited 是什麼？
visited 是一個布林陣列，例如：
bool visited[MAXN];
用來標記每個節點（課程）是否已經在 DFS 或 BFS 中拜訪過，避免重複走訪。
----------------------------------------------
問題二:visited 是什麼？
fill 是什麼？
fill 是 C++ STL 中的函式，定義於 <algorithm>，語法如下：
fill(起始位址, 結束位址, 要填入的值);
它會將指定範圍內的每個元素設為某個固定值。
----------------------------------------------
問題三:為什麼寫 visited + MAXN？
visited 是陣列的起始位址；
visited + MAXN 是陣列的結尾（不包含最後一個位置）；
所以 fill(visited, visited + MAXN, false); 就是把整個陣列的每個元素都設為 false。
你也可以用 for 迴圈寫：
for (int i = 0; i < MAXN; i++) {
    visited = false;
}
但 fill 寫法更簡潔，也更推薦使用於競賽或實務開發中。
----------------------------------------
小提醒：
在跑 DFS 或 BFS 前一定要清空 visited 陣列，否則會有上次紀錄殘留，導致錯誤的走訪判斷。
--------------------------------------
問題四:題目範圍值：
•        2 ≤N≤ 100 ,為什麼const int MAXN = 105;而不是100?
✅ 原因：預留緩衝空間以避免錯誤
雖然題目保證 N <= 100，但保險起見，開到 105 是為了避免以下幾種情況：
1. 程式陣列是從 1 開始而不是從 0
在許多競賽與練習中，課程編號或節點是從 1 到 N，例如課程 C1 ~ CN，而不是從 0 開始。

如果 N 是 100，實際上會使用到 arr[1] ~ arr[100]，總共需要 101 個空間。

若你剛好只開 int arr[100]，會導致 越界存取錯誤（undefined behavior）。

所以我們通常會多開一點，寫成：
const int MAXN = 105; // 實際只用到 arr[1] ~ arr[100]，但多一點更安全
2. 有些演算法會用到 N+1、或其他延伸用法
某些演算法（像是 BFS、DFS、Dijkstra）有可能會用到 N+1 或 MAXN-1 當作陣列索引的邊界。例如：
for (int i = 1; i <= N; i++) {
    // 訪問到第 N 個點，會使用 arr[N]
}
如果 N=100，你就會用到 arr[100]，所以你需要陣列大小是 101，但通常我們保險會開 105，以避免：

邊界出錯

未來測資擴增時需要重新修改上限

3.開多一點空間「幾乎不會有成本」
開個 int arr[105] 和 arr[100] 在效能和記憶體上幾乎沒差。

但可以大幅減少越界的風險，是一種實務與競賽習慣。
小結論：
為什麼開 MAXN = 105？        理由
課程/節點編號從 1 開始        arr[1]~arr[100] 需要 101 個空間
預防越界與未來擴充        更安全，避免錯誤
幾乎沒有記憶體成本        多 5 個 int 而已，影響極小
這就像買鞋子會買大半號一樣，是種安全與預留的習慣！



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://www.istak.org.tw/seed/) Powered by Discuz! 7.2