usaco-guide
usaco-guide copied to clipboard
cpinitiative
Contact Form Submission - Suggestion (Bipartite Matching)
Someone submitted the contact form!
URL: https://usaco.guide/dashboard
Module: None
Topic: Suggestion
Message:
It would be nice to add a module Maximum Bipartite Matching in the gold or platinum division.
sure, maybe platinum or advanced (it hasn't appeared in platinum for a while now). currently it's mentioned in the max flow module: https://usaco.guide/adv/max-flow?lang=cpp
~~don’t max flow and max matching reduce to each other?~~ doesn't max matching reduce to max flow?
no, you can't do max flow with max matching. also, the most naive max matching (O(NM)) is simpler to implement
oh yeah, i meant doesn't max matching reduce to max flow lol but i feel like this is still too small of a topic to warrant its own module but we do have like 5 modules just for dp who am i to say anything
but i feel like this is still too small of a topic to warrant its own module
maybe. though max matching is allowed by the IOI syllabus, whereas max flow is not.
Here are some notes about bipartite matching that would be good to include if we add such a module: https://colefranks.github.io/18453/lecturenotes/1-matching-notes.pdf