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