|
|
back to boardShow all messages Hide all messagesis 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). I got AC using bipartite matching :) I'm too - Hopcroft-Carp rulezz=) 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. 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. this algo is very similar to Dinica algorithm, are they identical? ну, не знаю даже! Кун прошел за 0.9 |
|
|
