ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1505. Перекачка нефти

WA31
Послано Alex Tolstov (Vologda STU) 16 сен 2009 13:15
Why?
Re: WA31
Послано Alex Tolstov (Vologda STU) 25 сен 2009 01:05
What is fucking test 31?? Does anybody know?
I use Dijkstra on residue network from several sources to sink.

For every edge (u, v):
1) if flow < capacity then cost = 0
2) if flow > 0 then graph contains back edge (v, u) with cost = 0.

Dijkstra initialize sources (nodes of the graph, where excess of flow > 0) with cost = 0. We find shortest path from one of sources to the sink. Then we make changes with edges used in shortest path and out results.

What's wrong??