^[1] P3邏輯電路

題目看似複雜，但應該不難想到使用圖(Graph)相關的演算法處理，不外乎兩種:DFS/BFS。

我們把所有的輸入端口、邏輯閘、輸出端口都看成是節點，以此建立一個有向圖，題目要求是終端的訊號，從終端開始往前推會比從端口出發來的有效率，因此把每個終端當做根節點(Root)，作DFS一直遍歷到葉節點，就能求出終端的訊號。

以下程式碼為資料的輸入，圖的儲存方式使用Adjacency Lists。
若還沒學過map可以用二維陣列替代。

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，進入節點時，我們會遇到三種狀況:節點為輸入端口、邏輯閘、輸出端口

void dfs(int st){
    if 輸入
        return
    else if 邏輯閘
        dfs(子節點)
    else 輸出
        dfs(子節點)
}

新增一個一維陣列 mx[i]，表示以i為根節點的最大延遲時間->

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]

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才能先求出子節點的資料)

#### 完整CODE:

#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;

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]

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);" ↩︎