57 b 任何flow的流量|f| 一定小於等於任何cut的容量c(S,T)所以若有flow的流量剛好等於某個cut的容量 他一定是maxflowc 他的意思是flow的流量會被多少cut set bounded 我的想法是cut set的定義必須分開s跟t，那假設有n個點，扣掉s, t剩n-2個點每個點都可以選擇要分在S或T 總共的分法是2^{n-2}種所以應該是O(2^n)??loop invariant應該要解釋成：某個statement 不論loop執行到什麼階段 這個statement都為真 這樣會比較好理解其實這邊他就是要考輾轉相除法的原理是什麼也就是gcd(m,n) = gcd(n,r)對應到42就是A選項 因為這是一個定理 所以不論loop到什麼階段、m, n的值是什麼 都不會改變這個statement的正確性 所以他是這裡的loop invariantloop invariant可以用來驗證algorithm的正確性 可以這樣驗證
https://i.imgur.com/CDr3dab.jpg