1

Тема: Станки

Добрый день, помогите пожалуйста решить задачу, сразу на ум приходит решение Венгерским алгаритмом, однако вот в чём проблема:
----------------------------------------------------------------------------------------------------------------------------------------------------------
Не могу понять как найти максимальную производительность конвейера, у которого производительность равна минимуму производительности рабочих на станках. Т.к. Венгерский алгоритм ищет суммарную(минимальную или максимальную) производительность(затраты), и это не значит что мы получим максимальную производительность конвейера, т.е. минимум в  случае Венгерского алгоритма среди производительности рабочих на станках может быть меньше, чем если бы мы получили более меньшую суммарную "стоимость", но большие частные веса рабочих на станках, а значит и более производительный конвейер.
-----------------------------------------------------------------------------------------------------------------------------------------------------------

Задача


Условие

N различных станков один за другим связаны в конвейер. Имеется N рабочих. Задана матрица C размера N × N, где элемент матрицы Cij задает производительность i-ого рабочего на j-ом станке. Необходимо определить, каким должно быть распределение рабочих по станкам (каждый рабочий может быть назначен только на один станок; на каждом станке может работать только один рабочий), чтобы производительность всего конвейера была максимальной. Производительность конвейера, при некотором распределении рабочих по станкам, равна минимальной из производительностей рабочих на назначенных им на конвейере станках.

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

Входные данные

Входные данные находятся в файле input.in.
Первая срока содержит количество рабочих (станков) N (1 ≤ N ≤ 500).
Затем идут N строк файла, которые задают матрицу производительностей C (1 ≤ Cij ≤ 1000) (каждой строке матрицы соответствует отдельная строка входного файла, элементы в строках разделены пробелами).

Выходные данные

Выходные данные находятся в файле output.out.
Первая строка содержит максимальную производительность конвейера.
Вторая строка содержит номера станков, на  которые распределены рабочие 1, 2, …, N соответственно (элементы в строке разделены пробелами).

Пример
input.txt
3
7 8 9
9 5 6
10 6 8

output.txt
8
2 1 3