[Help] How do you recover a set of edges that form the minimum cut after running maximum flow?

Правка en3, от SuperSheep, 2023-02-01 05:45:24

I figured you'd have to check the edges that are saturated, and if there's a path of saturated edges with the same capacity, choose any of them. But I'm having trouble on cases where there may be many of those paths or the saturated edges are connected by non-saturated edges with higher capacity in between.

I came up with checking every path that has at least one saturated edge, but I think that would be too slow as it may check too many edges just to get one of the saturated ones, in something like $$$O(|minCutEdges| \cdot E)$$$.

How do you do it efficiently?

If it's relevant, I'm trying to solve this problem (can find the optimal profit but can't print the solution): szkopul — Travel Agency (biu)

Теги max-flow min-cut, flow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский SuperSheep 2023-02-01 05:45:24 0 (published)
en2 Английский SuperSheep 2023-02-01 05:43:26 8 Tiny change: 'nCutEdges|*E)$.\n\nHo' -> 'nCutEdges| \cdot E)$.\n\nHo'
en1 Английский SuperSheep 2023-02-01 05:42:36 896 Initial revision (saved to drafts)