приводится алгоритм.
сначало вычитаются минимальные элементы со строк. потом со столбцов. получаем не менее 1 нуля во всех строках и столбцах
далее есть пункт:
1. Провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.

а подход как это сделать, не дан.
сначала попробовал метод — по порядку выирается строка иил столбец с максимальным кол-вом нулей. не подошло.
потом попробовал — находим строку (столбец) с минимальным кол-вом нулей, и среди столбцов (строк) где есть 0 элемент в выбранной строке (столбце), ищем столбец (строку) с максимальным количеством нулей, его и вычеркиваем. вроде правильно решало, но снова нашелся контр пример.

так как здесь поступить?

Здравствуйте, ilnar, Вы писали:

I>1. Провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.
Это задача о построении минимального вершинного покрытия в двудольном графе.

А именно, в одной доле графа окажутся строки, а другой -- столбцы. Ребро будет соединять две вершины графа (строку и столбец), если и только если на их пересечении стоит ноль. Искомое подмножество строк и столбцов обладает тем свойством, что покрывает все нули (ребера). следовательно мы ищем вершинное покрытие минимального резмера.

Покрытие это можно найти предварительно найдя т.н. "максимальное паросочетание" в этом графе. Сделать это можно за полиномиальное время (например, за O(n^3)). Учитывая, что всю эту деятельность нужно будет проделывать O(n) раз, получаем общую оценку сложности O(n^4). В принципе это очень медленно и можно улучшить как минимум в n раз, если инкрементально строить вершинные покрытия на каждой итерации.

I>так как здесь поступить?
Искать по ключевым слоовам "assignment problem", "hungarian algorithm", "maximum matching", "minimum vertex cover". То описание, что у тебя есть, мягко говоря не полное. Некоторое неплохое изложение, как помню, было в книге Липского "Комбинаторика для программистов".

Здравствуйте, Mab, Вы писали:

мне как раз надо решение задачи о назначениях заданной в матричном виде. не в векторно графовых понятиях.

поэтому интересует не алогритм решения, а подход к 1-му пункту, а именно как минимальным количеством линий покрыть все нули?

Здравствуйте, ilnar, Вы писали:

I>мне как раз надо решение задачи о назначениях заданной в матричном виде. не в векторно графовых понятиях.
Не суть.

I>поэтому интересует не алогритм решения, а подход к 1-му пункту, а именно как минимальным количеством линий покрыть все нули?
Я же объяснил, к какой задаче все это сводится. Дальше можно почитать книжки или поискать в инете.