I’m trying to solve this problem, I tried two different ways to solve it, but I got wrong answer for both of them.
- First way: delete from the graph all edges that don’t belong to a path of length <= k, then run max-flow min-cut. code
- Second way: run max-flow min-cut using Ford–Fulkerson method, and I will stop when the shortest path between the source and the sink is bigger than 2*k (here I multiply k by 2 because there’s an extra edge for every node to save its own capacity). code
Please can anyone tell me what’s wrong in my ideas? And can anyone give an idea to solve this problem?
UPD: Any help please?