Part One:
All Hands on Deck
You've navigated through the wormhole and arrived just outside of the Aurawroughts' secret base, successfully avoiding detection by enemy ships. Captain Xarlos calls all hands to the Main Deck. The ship's high-powered laser needs to be manned for the upcoming attack, and your assistance is needed to coordinate the crew's route to the deck.
The hallways leading to the Main Deck have different capacities, allowing varying numbers of crew members to pass through simultaneously.
Starting from the source, Storage Room 1 (S1), the crew must choose their paths through the hallways, passing other storage rooms or junctions, to reach the destination, the Main Deck (MD). Captain Xarlos emphasizes the need for fast, efficient movement and requests a calculation of the maximum flow — the greatest number of crew members that can move through the hallways at one time.
You quickly annotate the floor plan on your holographic tablet, listing each hallway as a pair of connected rooms separated by a hyphen, followed by a space and the hallway's capacity — this serves as your puzzle input.
It's crucial that no crew members linger in any room or hallway, as this would restrict the flow. The entire crew that starts from the source (S1) must travel to the destination (MD) and arrive together. Captain Xarlos awaits your calculation of the maximum number of crew members that can flow through the hallways simultaneously so he can efficiently instruct his sizable crew.
For example:
With your source at A, your destination at
F, and a floor plan like
A-B 3
A-C 3
B-C 2
B-D 3
C-E 2
D-E 4
D-F 2
E-F 3
Your task is to find the paths that allow the greatest number of crew members to reach the destination, given the capacity limits of the hallways.
Demonstrated in the animation above, you can see the best paths to achieve the maximum possible flow from the source to the destination.
Identifying the most efficient path selection allows you to determine that the maximum flow for this floor plan is 5.