Problem B
Is really solution O(n^2) exists ?
Re: Problem B --> Yes of course, it's maximum matching
> Is really solution O(n^2) exists ?
Re: Problem B
> > Is really solution O(n^2) exists ?
> Yes of course, it's maximum matching
Sure, it it's maximum matching (maximum independent set in
bipartite graph acutally), but how do you solve it in O
(n^2)? Best known algorithm is O(n^2.5) afaik.
Re: Problem B --> very simple, it base on maximum flow !
> > > Is really solution O(n^2) exists ?
>
> > Yes of course, it's maximum matching
>
> Sure, it it's maximum matching (maximum independent set
in
> bipartite graph acutally), but how do you solve it in O
> (n^2)? Best known algorithm is O(n^2.5) afaik.
Re: Problem B --> IS REALLY O(n^2)?? i know only O(n^3) and a little about O(n^2.5)... :(
> > > > Is really solution O(n^2) exists ?
> >
> > > Yes of course, it's maximum matching
> >
> > Sure, it it's maximum matching (maximum independent set
> in
> > bipartite graph acutally), but how do you solve it in O
> > (n^2)? Best known algorithm is O(n^2.5) afaik.
Re: Problem B --> very simple, it base on maximum flow !
Could you send me your solution to aksonov@mail.ru ? i've
wrote program based on maximal flow, but "Time Limit"....
My algorithm is O(n*k) and i don't know better algorithm.
Thanks,
Pavel.
Re: Problem B --> very simple, it base on maximum flow !
You should optimize the network flow and it will be fast
enough - use adjacentcy lists etc. or try the algorithm
that finds augmenting paths that alternate and then flips
the edges.
Thanks. I will. You give me good hope :)
> You should optimize the network flow and it will be fast
> enough - use adjacentcy lists etc. or try the algorithm
> that finds augmenting paths that alternate and then flips
> the edges.
