[олимпиадное программирование]Задачка

0

0

Собственно вот условие: http://pastebin.com/xxi2Eqqa

Сам я пробовал писать максимальный поток минимальной стоимости(не проходило по времени) и пробовал сортировать рёбра по цене и идти от бОльшего к меньшему(это, естественно, неправильно решение).

Может, у кого-нить есть другие идеи и он готов поделиться?

Ссылка

←	Линус хочет сменить нумерацию релизов ядра

[математикам] Восстановление поверхности по нормалям

→

Я думаю, лор не особо олимпиадниками богат..

А откуда задачка?

initab
(23.05.11 23:53:49 MSK)

Ответ на: комментарий от initab 23.05.11 23:53:49 MSK

А откуда задачка?

В универе предмет такой есть. Просто я сам немного бывший олимпиадник - но эту задачу что-то не могу побороть

hired777 ★
(23.05.11 23:55:37 MSK) автор топика

Ссылка

В каком месте она олимпиадная? Обычный алгоритм потоков не катит? Граф то маленький получается совсем.

~~dikiy~~ ★★☆☆☆
(24.05.11 00:01:34 MSK)

Это же транспортная задача.

elverion
(24.05.11 00:03:41 MSK)

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

metar ★★★
(24.05.11 00:06:11 MSK)

Ответ на: комментарий от elverion 24.05.11 00:03:41 MSK

Скормил входные данные своей лабе по исслопу, получил ответ 110. чтд

elverion
(24.05.11 00:11:58 MSK)

Ссылка

Ответ на: комментарий от dikiy 24.05.11 00:01:34 MSK

Обычный алгоритм потоков не катит?

Я же написал в исходном сообщении, что не укладывается по времени

hired777 ★
(24.05.11 00:24:00 MSK) автор топика

Ответ на: комментарий от metar 24.05.11 00:06:11 MSK

венгерский алгоритм

Вот это похоже на правду. Почитаю на днях. Спасибо!

hired777 ★
(24.05.11 00:24:29 MSK) автор топика

Ссылка

Ответ на: комментарий от metar 24.05.11 00:06:11 MSK

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

Что-то непохоже.

elverion
(24.05.11 00:30:51 MSK)

Ссылка

Ответ на: комментарий от hired777 24.05.11 00:24:00 MSK

http://tuprints.ulb.tu-darmstadt.de/epda/000822/np.pdf

Быстро нагуглил алгоритмы разные. Там на 16 странице обзор со сложностью есть.

~~dikiy~~ ★★☆☆☆
(24.05.11 00:37:22 MSK)

Ответ на: комментарий от metar 24.05.11 00:06:11 MSK

задача о назначениях => венгерский алгоритм

Это не задача о назначениях.

hired777 ★
(24.05.11 00:40:58 MSK) автор топика

Ответ на: комментарий от dikiy 24.05.11 00:37:22 MSK

http://tuprints.ulb.tu-darmstadt.de/epda/000822/np.pdf

Быстро нагуглил алгоритмы разные. Там на 16 странице обзор со сложностью есть.

Это просто поток. А мне нужен поток мин стоимости. Или другое решение.

hired777 ★
(24.05.11 00:42:48 MSK) автор топика

Ответ на: комментарий от hired777 24.05.11 00:42:48 MSK

А что если вместо двух весовых коеффициентов (стоимость и прокускная способность) один ввести - эффективность. И по нему рассчитывать?

~~dikiy~~ ★★☆☆☆
(24.05.11 00:45:24 MSK)

Ссылка

Ответ на: комментарий от hired777 24.05.11 00:40:58 MSK

> Это не задача о назначениях.
Верно, я читал в полглаза.)

максимальный поток минимальной стоимости (не проходило по времени)

Других вариантов не вижу. Можно попробовать ускорить поиск пути, как вы это сейчас делаете?

metar ★★★
(24.05.11 00:57:09 MSK)

Классическая же задачка...
А если её симплекс-методом, не катит?

Xenius ★★★★★
(24.05.11 21:51:56 MSK)

Ссылка

Ответ на: комментарий от metar 24.05.11 00:57:09 MSK

максимальный поток минимальной стоимости (не проходило по времени)

Других вариантов не вижу. Можно попробовать ускорить поиск пути, как вы это сейчас делаете?

http://e-maxx.ru/algo/min_cost_flow

hired777 ★
(25.05.11 00:01:50 MSK) автор топика

Ссылка

Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.

←	Линус хочет сменить нумерацию релизов ядра

[математикам] Восстановление поверхности по нормалям

→