The purpose of this problem is a practice of viewing the problem as a Linear Programming (LP) and using the technique of considering its dual.

---

A formulation as a Linear Program

Let \(l_i\) be the number of cameras installed in the \(i\)-th vertex to the left,
and \(r_i\) be the number of cameras installed in the \(i\)-th vertex to the right.
Then this problem asks to minimize

\(\sum_i A_il_i + \sum_i B_ir_i\)

subject to

\(l_i+r_j \ge C_{i,j}\),

\(l_i \ge 0\),

\(r_i \ge 0\), and

\(l_i,r_i \in \mathbb{Z}\).

Here, we can prove that we can ignore the conditions of integerness (\(l_i,r_i \in \mathbb{Z}\)) and optimize within the range of real numbers. (Proof will be shown later)

Therefore, we now see that the problem can be written as follows.

\(\mathrm{minimize} \sum_i A_il_i + \sum_i B_ir_i\)
\(\mathrm{subject\ to}\) \(l_i+r_j \ge C_{i,j}\), \(l_i \ge 0\), \(r_i \ge 0\) (The variables can be any real numbers)

For a given set of variables of real numbers, a problem of optimizing a linear expression under the constraints defined by a series of linear inequalities is called a Linear Program.

---

Obtaining the dual

Let us consider the obvious lower bound of the objective function (\(\sum_i A_il_i + \sum_i B_ir_i\)). First, since we know that

\(l_i+r_j \ge C_{i,j},\)

we can see that multiplying a non-negative real-number coefficient \(k_{i,j}\), resulting in

\(k_{i,j}(l_i+r_j) \ge k_{i,j} C_{i,j},\)

is satisfied too. In general, for a non-negative real-number coefficients \(k_{i,j}, p_i, q_i\), we can see that the linear combination of the constraints

\(\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i \ge \sum_{i,j} k_{i,j} C_{i,j}\)

is also satisfied. Especially, if the left hand side of the inequality above is equal to the objective function, then the right-hand side of the inequality above gives an obvious lower bound of the objective function.

The duality theorem claims that the best of the obvious lower bounds obtained by the steps above is actually the optimal solution. That is, the answer is the maximum of

\(\sum_{i,j} k_{i,j} C_{i,j}\)

under

\(\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i = \sum_i A_il_i + \sum_i B_ir_i.\)

This is equivalent to as follows.

\(\mathrm{maximize} \sum_{i,j} C_{i,j}k_{i,j}\)
\(\mathrm{subject\ to}\)
\(\sum_i k_{1,i} \le A_1\) , \(\sum_i k_{2,i} \le A_2, \dots, \sum_i k_{L,i} \times A_L\)
\(\sum_i k_{i,1} \le B_1\) , \(\sum_i k_{i,2} \le B_2, \dots, \sum_i k_{i,R} \times B_R\)
For all \(k_{i,j}\), \(k_{i,j} \ge 0\)

Solving the dual problem

This dual problem can be solved as a minimum cost flow problem.

Prepare Vertex \(U_i\) for every \(1 \le i \le L\) and Vertex \(U_i\) for every \(1 \le i \le R\), accompanied by special Vertices \(S\) and \(T\), and add the following edges.

• Add an edge from \(S\) to \(U_i\) with maximum capacity \(A_i\).
• Add an edge from \(U_i\) to \(V_j\) with no maximum capacity. If there are some flow in this edge, then you can claim \(C_{i,j}\) bonus per flow of \(1\).
• Add an edge from \(V_i\) to \(T\) with maximum capacity \(B_i\).

You may augment flow from \(S\) to \(T\) as much as you want. What is the maximum bonus you can claim?

This problem can be solved as a minimum cost flow problem, of which the implementation is available in ACL (AtCoder Library) as well.

The proof of integerness

Suppose that an optimal solution has non-integer variables. Then, for a sufficiently small variable \(\delta\), after adding \(+\delta\) all the non-integer variables to the left, and adding \(-\delta\) to all the non-integer variables to the right, the constraints will still be satisfied, and the delta of the objective function is a linear function of \(\delta\). By shifting \(\delta\) in the direction that does not decrease this linear expression until some variable hits to an integer, one can obtain an optimal solution with more number of integer variables. By repeating this operation, we can prove that there exists an integer in which all variables are integer.

Minimum vertex cover and maximum independent set of bipartite graphs

This problem is a generalization of minimum vertex cover of a bipartite graph. There is a theorem that, on a bipartite graph, the minimum vertex cover and the maximum matching is equal, which often appears in contests. (The proof is the simple case of this problem.) Also, on a general graph, a vertex set is an independent set if and only if its complement set is a vertex cover, so the maximum independent set on a bipartite graph is (number of vertex) - (maximum matching). This theorem is often seen in contests as well.

Related articles

If you want to learn dualities more, refer to slide this slide (in Japanese) .