У меня такая задача с COCI(2006-2007, 1st contest). Грубо говоря условия такие: есть N парней и N девушек. Для каждой пары известна вероятность того что они сойдутся. Нужно распределить всех по парам так, чтобы конечная вероятность того что все сойдутся была наибольшая. конечная вероятность будет высчитыватся подобным образом: перемножением всех вероятностей и делить на (N * 100).
Входные данные:
Число N (1 <= N <= 20) и матрица N * N. Число в i-ой строке и в j-ом столбце означает вероятность того что i-ый парень и j-ая девушка сойдутся в паре. Нельзя одного парня объеденить в паре с двумя девушками или более. Аналогичная ситуация с девушками.
Выходные данные:
Конечная вероятность того что все пары сойдутся. Ответ считается правильным если погрешность меньше 10^-6.