Gem Shop Lighting
Time limit5sMemory limit128 MB
Given required light values for an N by M grid of gems, find the minimum total intensity of row and column lamps so every gem's light requirement is met, which reduces to a maximum weight bipartite matching problem.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Matrix
- Solved
- No attempts yet
Problem
Hyeongtaek runs a gem shop. The gems are arranged in an N × M grid. Each row has one row lamp that lights the gems in that row, and each column has one column lamp that lights the gems in that column. There are N row lamps and M column lamps in total.
Each gem has a minimum amount of light it must receive to keep its best appearance, and this value can be different for every gem. The following table shows the required light values for gems arranged in a 2 × 3 grid.
The light received by the gem at position (i, j) is the sum of the intensity of row lamp i and the intensity of column lamp j. You must choose the intensity of every row lamp and column lamp so that every gem receives at least its required amount of light.
If the column-lamp intensities are 2, 0, 1 and the row-lamp intensities are 1, 1, then the received light values are as follows.
All gems satisfy their requirements, and the total lamp intensity is 2 + 0 + 1 + 1 + 1 = 5, which is minimal.
Given the required light value of each gem, find the minimum possible sum of intensities of all row lamps and column lamps while satisfying every requirement.
Input
The first line contains two positive integers N and M. Both values are at most 256.
Each of the next N lines contains M positive integers, where each integer is the required light value of one gem. Every given value is at most 2,000,000.
Output
Output the minimum possible total intensity of all row lamps and column lamps while satisfying the requirements.