основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Помогите найти задачу!
      #12023 - 09/04/06 06:44 AM

Никто не знает, где предлагалась такая задача:
Дан граф, причём некоторые рёбра ориентированы, а некоторые - нет.
Требуется, если возможно построить в нем Эйлеров цикл, причём по ориентированным рёбрам можно двигаться только в одном направлении.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
kia
новичок
*****

Рег.: 06/12/06
Сообщений: 21
Re: Помогите найти задачу! [Re: EfremovAleksei]
      #12024 - 09/04/06 07:09 AM

http://acm.uva.es/p/v107/10735.html

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
it4_kp
опытный
*****

Рег.: 03/31/05
Сообщений: 221
Из: Архангельск
Re: Помогите найти задачу! [Re: kia]
      #12026 - 09/04/06 09:42 AM

Кстати, интересно получилось...

Я решил эту задачу, но совсем не так как ты говорил на испанском форуме...
Сложность моего алгоритма O(V^3). Т.е. никак не зависит от E, а твоего, насколько
я понял O((V+E)^2.5).


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
kia
новичок
*****

Рег.: 06/12/06
Сообщений: 21
Re: Помогите найти задачу! [Re: it4_kp]
      #12030 - 09/04/06 04:36 PM

У моего решение сложность O(V^3 + (V+E)V), можно улучшить до O((V+E)^1.5).
А как ты решал?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
it4_kp
опытный
*****

Рег.: 03/31/05
Сообщений: 221
Из: Архангельск
Re: Помогите найти задачу! [Re: kia]
      #12033 - 09/04/06 10:27 PM

В ответ на:

А как ты решал?



Сначала проверил чтобы у каждой вершины была четная степень,
если все ребра понимать как неориентированные, а также, чтобы
у каждой вершины хватило неориентированных ребер, чтобы покрыть
недостаток или избыток входящих ребер.

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

Нашел макс. поток из источника в сток (отсюда сложность O(V^3)) по
неориентированным ребрам. Поток сам сделал нужные ребра ориентированными.

Ну и, наконец, одним dfs нашел цикл.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Re: Помогите найти задачу! [Re: it4_kp]
      #12047 - 09/06/06 06:13 AM

Подскажите, пожалуйста, ещё задачи на макс. поток и на макс. поток мин. стоимости.
Желательно, из архивов с online проверкой.
А кстати, Кредитные операции-2 с Тимуса никто не решал?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 430 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 13102

Rate this topic

Переход в