BackmediumUncategorized uncategorized medium

Cost-Optimized Directed Flow Solution

Problem Statement

You are given a directed graph with `N` nodes and `M` edges. Each edge `(u, v)` has an associated maximum flow capacity `C(u, v)` and a cost `W(u, v)` for each unit of flow sent through it. Your task is to find the minimum total cost to send exactly `F` units of flow from a designated source node `S` to a designated sink node `T`. The total cost of sending flow through an edge is `flow_sent * W(u, v)`. The flow must adhere to standard network flow rules: 1. Flow conservation: For any intermediate node (not S or T), the total flow entering the node must equal the total flow leaving it. 2. Capacity constraint: The flow through any edge `(u, v)` cannot exceed its capacity `C(u, v)`. 3. All `F` units of flow must successfully reach the sink node `T` from the source node `S`. If it's impossible to send exactly `F` units of flow from `S` to `T`, return -1.

Example 1

Input

N = 3, M = 3, S = 0, T = 2, F = 2 Edges: [[0,1,1,5], [0,1,1,2], [1,2,2,1]] (Edge format: [source, sink, capacity, cost])

Output

Explanation: Send 1 unit via path 0->1 (using the edge with cost 2) -> 2 for a total cost of 1*(2+1) = 3. Remaining flow needed is 1 unit. Send the remaining 1 unit via path 0->1 (using the edge with cost 5) -> 2 for a total cost of 1*(5+1) = 6. Total cost is 3 + 6 = 9.

Constraints

`2 <= N <= 100` (Number of nodes)
`1 <= M <= 1000` (Number of edges)
`0 <= S, T < N`, `S != T` (Source and Sink nodes)
`0 <= F <= 1000` (Total flow required)
For each edge `(u, v, capacity, cost)`:
- `0 <= u, v < N`
- `1 <= capacity <= 500`
- `0 <= cost <= 100`

Cost-Optimized Directed Flow Solution

Problem Statement

Input

Output

Constraints

More Uncategorized Problems

Optimized Approach

Step-by-Step Dry Run

Tested Solutions