2. Maximum Matchings via MaxFlow

Getting Started with Competitive Programming

(an NPTEL course)

Module 2. Maximum Matchings via MaxFlow

We introduce here a classic idea — solving maximum matchings in bipartite graphs by reducing it to maximum flow. In some situations you might want to use a more direct approach to this problem, however, this is easy to do and works often! The larger point here is to demonstrate the point that the maxflow algorithm can be used to solve many problems that are unrelated to finding maximum flows.

The code in this lecture can be found here, and it solves the BerSU Ball problem on Codeforces.

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>