# 台大 106 軟體
###### tags: `NTU` `106` `軟體`
1. (a) O(lgn) (b) O(n) \(c\) O(n) (d) lgnlglgn
2. (a) yes (b) no, 372 不該出現在 355 的右子樹 \(c\) yes
3. 3A: len[i-1,j-1]+1, 3B:A,prev,i-1,j-1, 3C:A[i]
4. 令 G=(V,E)，其中 $V=\{v_1,v_2,v_3,...,v_n\}$ 為所有城市的集合，E 為所有城市間的有向邊的集合。
(a)
令 $V'=\bigcup_{i=1}^{n}\{v_i^{in},v_i^{out}\}$
令 $E'=\bigcup_{i=1}^{n}\{(v_j^{out},v_i^{in})\ |\ (v_j,v_i)\in E\}\ \cup\ \{(v_i^{out},v_k^{in})\ |\ (v_i,v_k)\in E\}\ \cup\ \{(v_i^{in},v_i^{out})\}$
令 $r((v_i^{in},v_i^{out}))=c(v)$
令 capital 為 $v_1$，以 $v_1^{in}$ 為起點，對 G'=(V',E') 做 Dijkstra 演算，每個 $v_i^{out}$ 的最短路徑，即為題目要求之 $M(v_i)$
(b)
分析:
此題需考慮每個點的權重，是最短路徑問題的變形。
只需把「點的權重」轉化為「邊的權重」，即可用最短路徑演算法求解。
做法是將每個點 $v$ 分割成兩個點： $v_{in}$ 與 $v_{out}$。將所有 $v$ 的入邊與 $v_{in}$ 連接，將所有出邊 與 $v_{out}$ 連接。然後在 $v_{in}$ 與 $v_{out}$ 間建一條邊，令其權重為 $v$ 的點權重 $c(v)$。
時間複雜度: O(ClgC + R)

5.
(a) 令 $L=$ 所有課程的集合，$R=$ 所有教室的集合。令 $V=L\ \cup\ R\ \cup\ \{s,t\}$ $E=\{(c_i,r_j)\ |\ c_i\in L,r_j\in R,(c_i,r_j)\in M\}\ \cup\ \{(s,c_i)\ |\ c_i\in L\}\ \cup\ \{(r_j,t)\ |\ r_j\in R\}$
令 $c:E\rightarrow R$ 為容量函數。令 $c(s,c_i)=c(r_j,t)=1,\ \forall c_i\in L,\forall r_j\in R$，$c(c_i,r_j)=\infty,\ \forall c_i\in L,\ r_j\in R,\ (c_i,r_j)\in E$
對 $G=(V,E,c)$ 求最大流，即為題目所求

(b)