### [^1] [P3邏輯電路](https://zerojudge.tw/ShowProblem?problemid=m933) 題目看似複雜，但應該不難想到使用[圖(Graph)](https://web.ntnu.edu.tw/~algo/Graph.html)相關的演算法處理，不外乎兩種:[DFS](https://yuihuang.com/dfs-depth-first-search/)/BFS。 我們把所有的輸入端口、邏輯閘、輸出端口都看成是節點，以此建立一個有向圖，題目要求是終端的訊號，從**終端開始往前推**會比從端口出發來的有效率，因此把每個終端當做**根節點**(Root)，作DFS一直遍歷到葉節點，就能求出終端的訊號。 以下程式碼為資料的輸入，圖的儲存方式使用Adjacency Lists。 若還沒學過[map](https://www.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/)可以用二維陣列替代。 ```=C++ int p, q, r, m; //v[i] 表示節點i的輸出訊號，-1為無訊號 vector<int> v(60005, -1); int t[50005]; //邏輯閘 //mp[i]表示i的訊號來源，最多為2個:mp[i][0], mp[i][1] map<int, vector<int>> mp; cin >> p >> q >> r >> m; for(int i=1;i<=p;i++) cin >> v[i]; for(int i=1;i<=q;i++) cin >> t[i]; for(int i=0;i<m;i++){ //start連到end，end的訊號來源加上start int start, end; cin >> start >> end; mp[end].push_back(start); } ``` 接者開始DFS，進入節點時，我們會遇到三種狀況:節點為輸入端口、邏輯閘、輸出端口 ```=C++ void dfs(int st){ if 輸入 return else if 邏輯閘 dfs(子節點) else 輸出 dfs(子節點) } ``` 新增一個一維陣列 mx[i]，表示以i為根節點的最大延遲時間-> ```=C++ vector<int> mx(60005, -1); void dfs(int st){ if 輸入端口 mx[st] = 0; return; else if 邏輯閘 dfs(子節點); mx[st] = 1 + max(mx[子節點]) else 輸出端口 dfs(子節點); mx[st] = mx[子節點]; } ``` 同時計算訊號v[i] ```=C++ void dfs(int st){ if 輸入端口 else if 邏輯閘 dfs(子節點); //not v[st] = !v[子節點]; //and v[st] = v[子節點1] && v[子節點2]; //or v[st] = v[子節點1] || v[子節點2]; //xor:若不同則為正邏輯=>相同為正邏輯再顛倒 v[st] = !(v[子節點1] == v[子節點2]); else 輸出端口 dfs(子節點); v[st] = v[子節點]; } ``` 要注意這裡無論求訊號或延遲時間，**必須先DFS再計算**(先DFS才能先求出子節點的資料) :::spoiler #### 完整CODE: ```=C++ #include <bits/stdc++.h> using namespace std; int p, q, r, m; vector<int> v(60005, -1); vector<int> mx(60005, -1); int t[50005]; map<int, vector<int>> mp; ``` ```=C++ void dfs(int st){ if(st <= p) { mx[st] = 0; return; } if(mx[st] != -1) return; else if(st >= p+1 && st <= p+q){ if(t[st-p] == 4){ //not只有一個子節點 dfs(mp[st][0]); v[st] = !v[mp[st][0]]; mx[st] = 1 + mx[mp[st][0]]; }else{ int p1 = mp[st][0]; int p2 = mp[st][1]; dfs(p1); dfs(p2); if(t[st-p] == 1){ v[st] = v[p1] && v[p2]; } if(t[st-p] == 2){ v[st] = v[p1] || v[p2]; } if(t[st-p] == 3){ v[st] = !(v[p1]==v[p2]); } mx[st] = 1 + max(mx[p1], mx[p2]); } }else{ dfs(mp[st][0]); v[st] = v[mp[st][0]]; mx[st] = mx[mp[st][0]]; } } ``` ios::[^2] ```=C++ int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> p >> q >> r >> m; for(int i=1;i<=p;i++){ cin >> v[i]; } for(int i=1;i<=q;i++){ cin >> t[i]; } for(int i=0;i<m;i++){ //start連到end=>end的訊號來源有start int start, end; cin >> start >> end; mp[end].push_back(start); } int ans = 0; for(int i=p+q+1;i<=p+q+r;i++){ dfs(i); ans = max(ans, mx[i]); } cout << ans << endl; for(int i=p+q+1;i<=p+q+r;i++){ cout << v[i] << " "; } return 0; } ``` ::: [^1]:第三題和第四題通常會進入到演算法部分，不再像第一二題只考驗語法，有時候程式效率太差(過多的重複計算或效率不佳的演算法)也會導致該題只有拿到部分分，觀察資料上限大小判斷解題方法也是技巧之一。 [^2]:ios::sync_with_stdio(0); cin.tie(0); 此段程式旨在提高資料輸入的效率，通常在輸入大量資料時可考慮使用。若為輸出大量資料，可加上"cout.tie(0);"