Алгоритм генерации двоичной матрицы
Даны два входных массива [R1, ..., Rn] и [C1, ..., Cn]. Мы хотим создать двоичную матрицу A (размером nxn) так, чтобы сумма элементов в столбце i в A была Ci, а сумма элементов в строке j в A была Rj.
Я попытался заполнить, используя жадный алгоритм: заполнить 1 слева направо и уменьшить Ci и сделать это для каждой строки. Но это не сработало. (Кроме того, я попытался отсортировать строки и столбцы в порядке убывания, но все равно не получилось)
1 ответ
Это может быть решено с использованием максимальных потоков. Аналогичная (более сложная версия) проблема доступна на LightOJ, и мой код для справки
Вот решение.
Сначала мы создадим двудольный граф. Пусть количество строк будет no_rows и количество столбцов будет no_cols,
Теперь создайте no_rows + no_cols узлы. Устроить первый no_rows узлы слева (которые будут образовывать одну "часть" нашего двудольного графа). Давайте нумеруем эти узлы как l1, l2, ..., lno_row,
Точно так же устроим последний no_cols узлы справа (которые будут образовывать второе "раздельное"). Пронумеруем их как 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) края полностью заполнены.
Изменить: Вот реализация Dinic в C++ Ideone
Изменить 2: емкость края, соединяющего источник с любым li является Ri (где R является заданным входным массивом, указывающим суммы строк). Точно так же емкость края соединения ri тонуть T является Ci (где C это массив, указанный во входных данных с указанием сумм столбцов)