题目内容

Decide whether you think the following statement is true or false. Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$, and a positive integer capacity $c_e$ on every edge $e\ $. Let $(A, B) $ be a mimimum $s-t$ cut with respect to these capacities $\{c_e: e\in E\}$. Now suppose we add $1$ to every capacity, then $(A, B) $ is still a minimum $s-t$ cut with respect to these new capacities $\{1+c_e: e\in E\}$.

A. 正确
B. 错误

查看答案

搜索结果不匹配？点我反馈

更多问题

Coin is heads with probability 1/3 and tails with probability 2/3. The expectation of independent flips until first heads is _____.

A. 1
B. 2
C. 3
D. O($\log n$)

Decide whether you think the following statement is true or false. Let $G$ be an arbitrary flow network, with a source $s$, a sink $t$, and a positive integer capacity $c_e$ on every edge $e\ $. If $f\ $ is a maximum $s-t$ flow in $G\ $, then $f$ saturates every edge out of $s$ with flow (i.e., for all edges $e$out of $s$, we have$ f (e) = c_e$).

A. 正确
B. 错误

Gale-Shapley algorithm finds a stable matching in _____ time.

A. $O(n)$
B. $ O(n\log n)$
C. $O(n^2)$

$f(n) = \log n$ is ___; $g(n) = 2n + 1$ is _; $h(n) = f(n) + g(n)$ is ___.

A. $O(n); O(n); O(n)$
B. $\Omega(n); O(n^2); O(n)$
C. $O(n); \Omega(n^2); O(n)$