Ashen Relay Cut Problem

Ashen Relay Cut Problem — ExecCode Hard DSA Practice

Solve the Ashen Relay 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

Problem Statement There are N warehouses and M directed roads. Each warehouse has a capacity. Cargo that passes through warehouse i cannot exceed cap[i]. Each road has a lower bound and an upper bound: at least LO must go on that road at most HI may go on that road Send as much cargo as possible from warehouse S to warehouse T. If the lower bounds cannot be met, print -1. Warehouses are numbered from 1. Input Format There are exactly M road lines. Output Format One integer. The maximum amount from S to T, or -1. Constraints Use 64-bit integers. Example 1 Input There are 4 warehouses. Source is 1. Sink is 4. Every warehouse can pass 5. There are two ways to go from 1 to 4: 1 → 2 → 4 1 → 3 → 4 Each road can take at most 3. Warehouse 1 can send at most 5. Output Example 2 Input One road from 1 to 2. The road allows 10. Each warehouse allows only 1. Output Example 3 Input The only path is 1 → 2 → 3. Warehouse 2 allows only 1. Output

Examples

Input 4 4 1 4 5 5 5 5 1 2 0 3 2 4 0 3 1 3 0 3 3 4 0 3; Output 5. Input 2 1 1 2 1 1 1 2 0 10; Output 1. Input 3 2 1 3 2 1 2 1 2 0 5 2 3 0 5; Output 1

Constraints

1 ≤ N ≤ 80, 0 ≤ M ≤ 400, 0 ≤ LO ≤ HI ≤ 1e9, 0 ≤ cap[i] ≤ 1e9.

Practice Ashen Relay Cut free on ExecCode. Browse DSA problems, topic map, and placement guides.