DSAhardGraphs~40m

The Sold Out

Problem

You are an engineer on Spotify's concert ticketing team. Fans across cities want to attend concerts at various venues. The distribution network is modeled as a directed graph where each edge has a maximum capacity — the number of fans or tickets that can flow through it.

Given a directed graph with n nodes (0 to n-1), where node 0 is the source (Spotify's ticketing system) and node n-1 is the sink (total concerts attended), find the maximum number of fans that can attend concerts.

Each edge [u, v, capacity] means up to capacity fans can travel from u to v. Multiple edges between the same nodes have their capacities summed.

Examples

Example 1

Input: (4, [[0,1,10],[0,2,10],[1,3,10],[2,3,10]])

Output: 20

Two parallel paths: 0→1→3 and 0→2→3, each carrying 10 fans. Total: 20.

Example 2

Input: (4, [[0,1,100],[1,2,1],[2,3,100]])

Output: 1

The middle edge 1→2 has capacity 1 — it's the bottleneck regardless of other capacities.

Example 3

Input: (4, [[0,1,10],[0,2,10],[1,2,10],[1,3,10],[2,3,10]])

Output: 20

After path 0→1→2→3 saturates edge 1→2, the residual graph allows rerouting through 0→2→1→3 to recover the remaining 10.

Constraints

›2 <= n <= 100
›0 <= len(edges) <= 1000
›1 <= capacity <= 10^6
›No self-loops

Loading question…