search

cp-algorithms / cp-algorithms

Algorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)
https://cp-algorithms.com/
Creative Commons Attribution Share Alike 4.0 International
7.73k stars 1.62k forks source link

Problem on article "Maximum flow - Ford-Fulkerson and Edmonds-Karp" #1146

Closed luvgoyal45 closed 1 year ago

luvgoyal45 commented 1 year ago

Article: Maximum flow - Ford-Fulkerson and Edmonds-Karp

Problem:

jakobkogler commented 1 year ago

What's the problem?

luvgoyal45 commented 1 year ago

What's the problem?

The Problem attached below the article named "CSES-School Dance" is based on Kuhn's Algorithm and not Maximum Flow Algorithm. Also, there is a problem named CSES-Distinct Routes which is based on the algorithm and not mentioned in the practice problems.

jakobkogler commented 1 year ago

I've added the problem "CSES - Distinct Routes" to the page.

However I've also kept the School Dance problem, as it is possible to solve it with Max Flow. It's a simple version of the assignment problem.

Create a start node s and a target node t. Connect s with every boy, and t with every girl, and keep the k edges. Everything gets assigned a capacity of 1.