資料結構 403 選課App(難)

may

資料結構 403 選課App
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。



範例輸入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

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <algorithm>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. const int MAXN = 105;
   
8. vector<pair<int, int>> graph[MAXN]; // 存圖：{鄰接點, 權重}
   
9. bool visited[MAXN];
   
10. int countResult = 0;
    
11. int Q;
    
12. 
    
13. void dfs(int current, int minWeight) {
    
14.     visited[current] = true;
    
15.     if (minWeight >= Q) countResult++;
    
16. 
    
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. }
    
25. 
    
26. int main() {
    
27.     int N, k;
    
28.     cin >> N >> k >> Q;
    
29. 
    
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.     }
    
37. 
    
38.     // 初始化 visited 陣列
    
39.     fill(visited, visited + MAXN, false);
    
40. 
    
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.     }
    
50. 
    
51.     // 輸出結果（不包含自己）
    
52.     cout << countResult << endl;
    
53. 
    
54.     return 0;
    
55. }

複製代碼

回復 1# may

may

回復 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，不符合。
✅ 測資 3（所有課程都符合）
複製
編輯
輸入：
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

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

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

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

最後統計符合條件的課程數量（不包括自己）

may

回復 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 而已，影響極小
這就像買鞋子會買大半號一樣，是種安全與預留的習慣！