NxN matrix of 1s and 0s

Question

I am having a problem with task Im given NxN matrix with only 1s and 0s . In each step i generate random 1 in a row and a column of this 1 is closed. I need to find a minimum number of changes 0 to 1s to be sure that every row will be able to have one 1. For example

00

00

I need 2 changes to become

10

01

Or

000

110

000

I need 3 changes to make

110

110

001

so i can chose first or second 1 in first row. First or second in second row depanding on firsts row chose and 3rd 1 in 3rd row.

Answer 1

Consider your problem as a bipartite graph where we have workers on the left, jobs on the right, and edges if a worker can do a job.

Then compute the maximum matching of workers with jobs (e.g. with the Hopcroft-Karp algorithm).

If the matching is of size x, then we have successfully paired x workers with x jobs. We then need to spend n-x money to train the unmatched workers to do the unmatched jobs.