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

Обсуждение задачи 1389. Дорожные работы

biparite matching
Послано Baurzhan 14 авг 2009 10:57
is it possible to find biparite matching for n or n logn?
if we divide graph into 2 parts  - maximal matching is the answer. But biparite matching founding time is NM(max-flow) so N*N(because it's tree).
Re: biparite matching
Послано MarioYC 4 ноя 2010 11:47
I got AC using bipartite matching :)
Re: biparite matching
Послано Baurzhan 4 ноя 2010 16:42
I'm too - Hopcroft-Carp rulezz=)
Re: biparite matching in O(nlogn) ??????
Послано hoan 6 дек 2010 22:07
i use dynamic progrmaming and got AC in O(N), i think the best the algo too find maximum biprate matching ue O(nm), what's your algo?????

sorry for y poor english.
Re: biparite matching in O(nlogn) ??????
Послано Baurzhan 7 дек 2010 08:40
AFAIK, Fastest biparite matching algorithm - Hopcroft Carp, with complexity E*sqrt(V); V-num of vertices; E - num of edges; Given graph is a tree, so it's possible to color it into 2 colors, after that, take all black vertices as one part, white as other part and find max matching between them.
I can't give strict evidence of this approach but it intuitively understandable - just draw sample output on the paper and everything will become clear=) You can see my code -> i shared my account here http://acm.timus.ru/forum/thread.aspx?id=25749&upd=634266195834002500 Just look my submission.
Re: biparite matching
Послано Lavrentiy Palovich 6 июл 2011 17:48
this algo is very similar to Dinica algorithm, are they identical?
Re: biparite matching
Послано Lavrentiy Palovich 6 июл 2011 18:11
ну, не знаю даже! Кун прошел за 0.9