i'm looking for a well written, bug-free and fast code for the 
bipartite matching algorithm. can anyone share your code please?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Not my code but I think this is pretty good: http://zobayer.blogspot.com/2010/05/maximum-matching.html
thanks.
I want to share my version of bipartite matching, in the hope that, if it is wrong on certain test cases, someone would notice. It is not conventional, in the sense that the "Match" function has one loop instead of two. I have never noticed any notable difference, and the code is pretty short and encapsulated.
https://github.com/bicsi/code_snippets/blob/master/bipartite_match.cpp
Your implementation is O(VE) (and it is called Kuhn matching if I am not mistaken)
Do you have AC on these problems with this code?
http://www.spoj.com/problems/MATCHING/
http://mirror.codeforces.com/contest/722/problem/D
The last one it is intended to be greedy, but I got TLE with Kuhn and AC with Hopcroft-Karp
Both problems got accepted, without any substantial modifications to the algorithm. Link to the CF problem: http://mirror.codeforces.com/contest/722/submission/22865806
However, it seems that having the two "parts" of the bipartite graph swapped, I was getting TLE. Probably because at the same number of iterations, I was doing O(n * log(n)) work going through the bigger part, rather than O(n).
EDIT: It seems that a simple test comparing the two versions on the number of iteration of the outer loop on random test cases would easily prove / disprove the algorithm. I am, however, too lazy to do that right now :).