Z. Extras

Here are a few other problems you can try based on maximum flow.

  1. Bilingual on Google Code Jam (Round 2, 2015). As with many things, reducing to flow is not the only way to solve this problem, but it is the official solution. The editorial is missing information about setting up the source and sink vertices, you can try adding a source and making it adjacent to all English words from the first sentence and making all French words from the second sentence adjacent to a sink.
  2. CandyCupRunningCompetition on TopCoder. See here for hints.
  3. Brevity is Soul of Wit on Codeforces. This translates quite naturally to a biparitite matching problem. I haven't actually implemented this, so I am not sure if a flow-based implementation would work or not, but from the constraints I am optimistic.
  4. T-shirts Distribution on Codeforces. The flow network is quite natural here, but think about how you will recover information about the actual T-shirt assignment?
  5. Flawed Flow on Codeforces. This is a cute question in a flows context, but a solution is possible using, for examples, BFS.
  6. Petya and Graph on Codeforces. Think about how you would model the flow network here — it's not obvious and fun to work out!
  7. Array and Operations on Codeforces. Although the editorial recommends a direct approach to the maximum matching problem that emerges, a flow-based implementation also apparently goes through.