Проверьте, возможно ли создать двоичную матрицу. Когда дается сумма каждой строки и столбца?

Question

Учитывая сумму каждой строки и каждого столбца в матрице, проверьте, можно ли создать двоичную матрицу?

Ввод:

Первая строка ввода содержит два числа 1≤m, n≤100000000, количество строк и столбцов матрицы. Следующая строка содержит m чисел 0≤ri≤n - сумму каждой строки в матрице. Третья строка содержит n чисел 0≤cj≤m - сумма каждого столбца в матрице.

Выход:

Выведите «YES», если существует матрица «m-на-n» A, где каждый элемент равен 0 или 1. Иначе «NO».

Я использовал решение, опубликованное в Поиск, существует ли двоичная матрица с учетом сумм строк и столбцов

Вышеупомянутое решение отлично работает для небольших входных данных, но когда входное значение составляет порядка 1 миллиарда, тестирование становится таким, как время ожидания кодирования. Мне нужно решение, которое лучше, чем o (m * n). Может кто-то помочь, пожалуйста?

Answer 1

вы можете использовать алгоритм maxflow, он доступен в разных источниках, таких как https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/ или где-то еще.

для этой задачи вам нужно сделать график с 4 слоями;в первом и четвертом случае используйте только один узел, фактически они являются источником и местом назначения в алгоритме maxflow.

, а во втором и третьем уровне вы должны использовать узел m и n и между каждым узлом от одного уровня к другому уровнюэто ребро с емкостью = 1, это то, что вы назвали матрицей в своем вопросе.

, как мы уже говорили на втором уровне, у нас есть узел m, и все связано с первым узлом (источником в алгоритме maxflow), и этовеса - это то, что вы получаете в качестве входных данных.а для третьего и четвертого (узел назначения) то же самое с входными значениями m узла и m.

после запуска вашего алгоритма, если используется вся емкость узлов, поэтому ваш ответ - да, а если нет - ваш ответнет.Зачем?везде, где вы использовали емкость, в матрице показывается 1, и вам нужны все 1, поэтому ваш ответ должен иметь весь поток.и, как вы видите, между номером узла a из слоя secnod и nember b из третьего, если он имеет поток в вашей матрице m, m [a] [b] = 1.