ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1389. Roadworks

biparite matching
Posted by Baurzhan 14 Aug 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
Posted by MarioYC 4 Nov 2010 11:47
I got AC using bipartite matching :)
Re: biparite matching
Posted by Baurzhan 4 Nov 2010 16:42
I'm too - Hopcroft-Carp rulezz=)
Re: biparite matching in O(nlogn) ??????
Posted by hoan 6 Dec 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) ??????
Posted by Baurzhan 7 Dec 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
Posted by Lavrentiy Palovich 6 Jul 2011 17:48
this algo is very similar to Dinica algorithm, are they identical?
Re: biparite matching
Posted by Lavrentiy Palovich 6 Jul 2011 18:11
ну, не знаю даже! Кун прошел за 0.9