Question 12 Solution
COMP3121/9101 21T3 Final Exam
Copyright By PowCoder代写 加微信 powcoder
This document gives a model solution to question 12 of the final exam. Note that alter-
native solutions may exist.
1. You are given an n × n grid where some squares have exactly one flower (and the
others have none).
Design a polynomial time algorithm which determines whether it is possible to choose
exactly n squares so that each chosen square has a flower and no two chosen squares
are in the same column or in the same row.
You must provide reasoning to justify the correctness and time complexity of your
algorithm.
The input consists of the positive integer n, as well as an n × n array of booleans,
where the (i, j) element is TRUE if square (i, j) has a flower and FALSE otherwise.
The output is either YES or NO.
For example, suppose n = 5 and the grid is as follows.
Then the correct answer is NO.
However, if one extra flower were to be placed at (3, 3), the grid would be as follows.
In this case, the correct answer is YES.
Create a flow network with vertices as follows:
• source s and sink t,
• r1, . . . , rn representing the rows, and
• c1, . . . , cn representing the columns,
and edges:
• from the source to each ri with capacity 1,
• from each cj to the sink with capacity 1, and
• for each flower in row i column j, from ri to cj with capacity 1.
We find the maximum flow in this flow network using the Ford-Fulkerson algorithm.
If the maximum flow is n, output YES, and otherwise output NO.
There are 2n+2 vertices and at most n2+2n edges. The total outgoing capacity from
s is n, so the maximum flow is at most n. Therefore the running time of the Ford-
Fulkerson algorithm is O(|E||f |) = O(n3). The input contains n2 bits to describe the
grid, so this running time is clearly polynomial in the length of the input as required.
For correctness, observe that the maximum flow in this flow network is equal to the
size of a maximum bipartite matching in the underlying graph with vertices r1, . . . , rn
and c1, . . . , cn and edges corresponding to squares with a flower. In a matching, all
chosen flowers are in different rows and different columns. Therefore the answer is
YES if and only if a matching of size n exists.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com