Border Min Cut Problem

Border Min Cut Problem — ExecCode Hard DSA Practice

Solve the Border Min Cut problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

To isolate a capital (sink) from a port (source) you may shut directed pipes, paying their capacity. The cheapest shutdown is an s-t min cut, equal to the maximum flow by the max-flow min-cut theorem. Edges [u, v, capacity]. Return the minimum cut capacity from source to sink. You are given: n — nodes edges — directed capacities source — port sink — capital Return min-cut value. The cut is a partition, but only the capacity number is required.

Examples

Input {'n': 4, 'edges': [[0, 1, 3], [0, 2, 2], [1, 3, 2], [2, 3, 3]], 'source': 0, 'sink': 3}; Output 4. Input {'n': 2, 'edges': [[0, 1, 9]], 'source': 0, 'sink': 1}; Output 9. Input {'n': 3, 'edges': [[0, 1, 4]], 'source': 0, 'sink': 2}; Output 0

Constraints

Same network model as max flow Unreachable sink → 0

Practice Border Min Cut free on ExecCode. Browse DSA problems, topic map, and placement guides.