Задача про призначення
Задача про призначення
Задано квадратну матрицю з натуральних чисел порядку n. Виберіть n елементів з цієї матриці, так, щоб:
у кожному рядку і у кожному стовбці знаходився рівно 1 вибраний елемент;
з усіх наборів, які задовольеяють першу умову, сума вибраних чисел повинна бути найменшою.
Якщо таких наборів декілька — виведіть довільний.
Вхідні дані
У першому рядку записано натуральне число n (1 ≤ n ≤ 200). У кожному з наступних n рядків записано по n чисел. Кожен елемент матриці не перевищує 1000.
Вихідні дані
У перший рядок виведіть суму знайдениых чисел. У другий рядок виведіть n чисел. i-те число у послідовності повинно позначати такий номер стовбця, що на перетині i-го рядка і заданого стовбця стоїть вибраний елемент. Очевидно, ця послідовність повинна бути перестановкою чисел від 1 до n.
Приклад
5 7 10 5 3 7 10 6 6 10 9 7 7 7 5 9 5 1 4 7 7 5 10 6 5 6
23 4 3 1 2 5