CF1288F Red-Blue Graph

You are given a bipartite graph: the first part of this graph contains $ n_1 $ vertices, the second part contains $ n_2 $ vertices, and there are $ m $ edges. The graph can contain multiple edges. Initially, each edge is colorless. For each edge, you may either leave it uncolored (it is free), paint it red (it costs $ r $ coins) or paint it blue (it costs $ b $ coins). No edge can be painted red and blue simultaneously. There are three types of vertices in this graph — colorless, red and blue. Colored vertices impose additional constraints on edges' colours: - for each red vertex, the number of red edges indicent to it should be strictly greater than the number of blue edges incident to it; - for each blue vertex, the number of blue edges indicent to it should be strictly greater than the number of red edges incident to it. Colorless vertices impose no additional constraints. Your goal is to paint some (possibly none) edges so that all constraints are met, and among all ways to do so, you should choose the one with minimum total cost.

N/A

N/A