Алгоритм генерации двоичной матрицы

Question

Для двух входных массивов [R1, ..., Rn] и [C1, ..., Cn]. Мы хотим создать двоичную матрицу A (size-nxn), чтобы сумма элементов в столбце i из A была Ci и сумма элементов в строке j группы A была Rj.

Я попытался заполнить, используя жадный алгоритм: заполните 1 слева направо и уменьшите Ci и сделайте это для каждой строки. Но это не сработало. (Кроме того, я попытался отсортировать строки и столбцы в порядке убывания, но все равно не работал)

Answer 1

Это можно решить с помощью Максимальных потоков. Аналогичная (более сложная версия) проблема доступна на LightOJ, а мой код для reference

Вот решение.

Сначала мы создадим двудольный граф. Пусть число строк равно no_rows, а количество столбцов - no_cols.

Теперь создайте no_rows + no_cols узлов. Расположите первые no_rows узлы в левой части (которые образуют один «partite» нашего двудольного графа). Позволяет считать эти узлы l1, l2, ..., lno_row.

Аналогичным образом устраивают последние no_cols узлы справа (которые образуют второй «partite»). Позволяет указать их как r1, r2, ... , rno_cols.

Теперь добавьте ребер между каждым li и rj для всех 1 <= i <= no_rows и 1 <= j <= no_cols, ориентированных слева направо, с мощностью 1.

Теперь создать источник (S) и раковину (T) , Добавьте край единицы мощности, ориентированный от источника, к каждой вершине слева.

Аналогичным образом добавьте края емкости блока, ориентированные от каждой вершины справа, к раковине.

Теперь просто найдите Максимальный поток на этом графике. Теперь, если существует поток между некоторой li и некоторых rj, что подразумевает, что клетка (i, j) будет 1, в противном случае она будет иметь 0.

Примечание: Для того, чтобы гарантировать, что существует даже такое бинарная матрица, убедитесь, что каждый краев (S, l) и края (r, T) полностью заполнены.

---

Редактировать: Вот реализация Динич в C++ ideone

---

Edit 2: Способность края, соединяющей источник с любым li является Ri (где R является данный входной массив, указывающий суммы строк). Аналогичным образом, пропускная способность ребра, соединяющего ri тонуть T является Ci (где C является массив входных приведены в колонке с указанием сумм)