A video platform routes uploads from an ingest server to a storage server through a network of relays. Nodes are numbered 0 to n - 1, and links[i] = [from, to, capacity] means up to capacity megabits per second can flow from from to to. Traffic can be split across many routes.
Write maxThroughput(n, links, source, sink) that returns the most megabits per second that can flow from source to sink without any link carrying more than its capacity. source and sink are different.
Input: n = 4, links = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]], source = 0, sink = 3 Output: 5
Send 2 along 0 → 1 → 3, 2 along 0 → 2 → 3, and 1 along 0 → 1 → 2 → 3. Both links out of node 0 are then full.
Input: n = 3, links = [[0,1,4]], source = 0, sink = 2 Output: 0
Nothing reaches node 2.
2 <= n <= 1000 <= links.length <= 10001 <= capacity <= 10^5Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #481 Maximum Upload Throughput. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.