I'm studying Edmond's maximum matching algorithm and will write the code of this algorithm. Does anyone know where to verify?
I'm studying Edmond's maximum matching algorithm and will write the code of this algorithm. Does anyone know where to verify?
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
http://acm.timus.ru/problem.aspx?space=1&num=1099
Thank you very much!
This problem.
Good day to you,
I've collected a few problems, in which I used Max-matching (HK) so here is mine list
http://www.lightoj.com/volume_showproblem.php?problem=1171
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4851
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=4899
http://codeforces.com/gym/100820 /*PROBLEM A — Airport*/
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3975
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4696
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2079
http://www.spoj.com/problems/MATCHING/
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3235
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4406
http://www.spoj.com/problems/ADAPATH/
http://www.spoj.com/problems/ADACITY/
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3994
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3642
Hope it will help {and hope I didn't make any mistake in collecting}!
Good Luck & Have nice day
I think he means matching in general graph. It is O(N^3) as far as I know and might be too slow for some of the problems which you have solved with HK.
Edit: Okay, he means Edmond's algorithm. At least this is O(N^3), right? :D
there are couple of matching algorithms. For example, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.6.2804&rep=rep1&type=pdf
Wow, thank you! :)