# 台大 100 軟體
###### tags: `NTU` `100` `軟體`
.1. (a) $C_6=\frac{1}{6+1}\binom{12}{6}=132$
.2. (b) $O(1+lg(\alpha))$
.6.
(1) 將每個點 $v$ 折成兩個點：$v_{in}, v_{out}$，兩點間建一有向邊，容量為 1。
(2) 建一起始點 $s$，與所有 starting vertices 的 $v_{in}$ 間建一條有向邊$(s, v_{in})$，容量隨喜
(3) 建一終點 $t$，與所有位在邊界上的點的 $v_{out}$ 間建一條有向邊 $(v_{out},t)$，容量隨喜
(4) 對於每個點 v ，以及與其相鄰的點 u，建一條有向邊 $(v_{out}, u_{in})$ ，容量隨喜
(5) 求最大流，若最大流 ＝ starting vertices 的個數則代表存在 vertex-disjoint paths