Матриця NxN з 1s та 0s - алгоритм

У мене проблема з завданням Im заданий NxNматриця з тільки 1s і 0s. На кожному кроці i генерують випадкові 1 в ряд і стовпець цього 1 закривається. Мені потрібно знайти мінімальну кількість змін від 0 до 1, щоб бути впевненим, що кожен рядок зможе мати один 1. Наприклад

00

00

Мені потрібні 2 зміни

10

01

Or

000

110

000

Мені потрібно зробити 3 зміни

110

110

001

тому я можу вибрати перший або другий 1 у першому рядку. Перший або другий у другому ряду, депанджінг на першому ряду вибрав і 3-й у 3-му ряду.

Відповіді:

2 для відповіді № 1

Розгляньте вашу проблему як двосторонній графік, де ми маємо робітників ліворуч, робочі місця праворуч, і краю, якщо працівник може виконати роботу.

Потім обчислити максимальну відповідність працівників робочим місцям (наприклад, з алгоритм Хопкрофта-Карпа)

Якщо відповідність має розмір x, то ми успішно з'єднали x працівників з x роботами. Потім нам потрібно витрачати гроші n-x, щоб навчити незрівнянних працівників виконувати неперевершені робочі місця.

---