Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Задача о назначениях

(Время: 1 сек. Память: 16 Мб Сложность: 42%)

Одной из классических задач комбинаторной оптимизации является так называемая «задача о назначениях». Формулируется она следующим образом.

Есть n работников, пронумерованных числами от 1 до n, и n работ, также пронумерованных числами от 1 до n. Если i-ый работник выполняет j-ую работу, то ему выплачивается зарплата в размере cij денежных единиц. Необходимо найти такое назначение работников на работы (каждый работник выполняет ровно одну работу, каждая работа выполняется ровно одним работником), что суммарная зарплата работников минимальна (соответствующая сумма называется стоимостью назначения).

Напишите программу, решающую задачу о назначениях.

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10). Последующие N строк содержат по N чисел каждая. При этом j-ое число (i + 1)-ой строки равно cij (1 ≤ cij ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите минимальную возможную стоимость назначения.

Примеры

INPUT.TXTOUTPUT.TXT
12
1 2
2 1
2
22
1 2
3 4
5

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Перестановки
 Структуры данных
 Библиотека алгоритмов
 A. Анаграмма
 B. Следующая перестановка ...
 C. Перестановки
 D. Перестановки - 2
 E. K-перестановки
 F. Задача о назначениях
 G. Следующее число
 H. Степень перестановки
 I. Перетягивание каната
 J. Перестановки - 3

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru