卷別

資料結構與演算法

選擇

國立臺灣大學 2025 · 考試 · 第 14 題

(5 points) Let $G$ be an $n \times n$ grid graph, with each undirected edge having a certain weight. Specifically, the vertices of $G$ can be labeled as $(i, j)$ where $1 \le i, j \le n$ . There is an edge between $(i, j)$ and $(k, \ell)$ if and only if $|i - k| + |j - \ell| = 1$ . Suppose we want to compute the value of a minimum cut that separates $(1, 1)$ and $(n, n)$ . The value of a cut is defined as the sum of weights of all edges crossing the cut.

Four students proposed different ideas for solving this task. Let us examine their approaches and select all correct statement(s) below.

(A)
Student A: Some minimum cut must cut through at most $2n$ edges. Since there are $2n(n-1) \le 2n^2$ edges in $G$ , we can design a brute force algorithm that enumerates at most $\sum_{k=1}^{2n} \binom{2n^2}{k}$ subsets of edges and check: if the removal of those edges separates $(1, 1)$ and $(n, n)$ . Any such subset leads to a candidate for the minimum cut.
(B)
Student B: For some minimum cut, the crossing edges must form a monotonic path from $(n, 1)$ to $(1, n)$ . In other words, those edges form a path of exactly $2n - 2$ edges from $(n, 1)$ to $(1, n)$ . Thus, we can solve this problem via dynamic programming.
(C)
Student C: Why don't we simply compute a maximum flow and then turning it to a minimum cut? First, construct a flow network by letting $(1, 1)$ be the source and $(n, n)$ be the sink. For each undirected edge connecting $(i, j)$ and $(k, \ell)$ , create two directed edges in opposite directions, both with capacities equal to that edge's weight. By using Dinitz's (Dinic's) algorithm, the maximum flow from $(1, 1)$ to $(n, n)$ can be computed in $O(n^6)$ . Using the Max-Flow Min-Cut Theorem, the returned maximum flow value equals the value of the minimum cut.
(D)
Student D: To separate $(1, 1)$ and $(n, n)$ , for some minimum cut, the crossing edges must form a shortest path from the south-west border $WS := \{(i, 1) \mid 1 \le i \le n\} \cup \{(n, j) \mid 1 \le j \le n\}$ to the north-east border $NE := \{(i, n) \mid 1 \le i \le n\} \cup \{(1, j) \mid 1 \le j \le n\}$ . Thus, we can run the Bellman-Ford algorithm that seeks for any shortest path from a vertex in $WS$ to any vertex in $NE$ . Finally, the length of the shortest path is the value of the minimum cut.
(E)
None of the above choices.

標準解析

AI 已複查