Challenge 21: Maximum Bandwidth

OIT needs your help. eduroam is having some problems ¹ and the network engineers at OIT want you to help them figure out if their current network configuration has enough bandwidth to send data from a particular source to a specific destination. If not, then they can add some more NSA wireless routers to give a better user experience ². Otherwise, they can blame it on nargles.

For instance, given the network on the right, we have four nodes and five connections with varying bandwidth capacities. For instance, node 1 and 2 have a bandwidth of 20 and node 3 and node 1 have a bandwidth of 10. The total maximum bandwidth between the source (1) and the destination (4) is 25. This is because we can send bandwidth 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4, for a total of 25.

Your mission is to write a program that computes the maximum bandwidth between two given nodes in a network. For this problem, you can assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world).

Input¶

You will be given a series of networks. The first line of the input specifies the number of nodes in the network (2 <= n <= 100). This is followed by a line that contains the source, target, and total number of connections. After this, you will be given the specification for each connection in the form of node 1, node 2, and capacity.

The final network will specify 0 nodes and should not be displayed.

Example Input¶

This is the sample input that corresponds to the image above:

4
1 4 5
1 2 20
1 3 10
2 3 5
2 4 10
3 4 20
0

Output¶

For each network configuration, print the network number (starting with 1) and the maximum bandwidth as shown below.

Example Output¶

Network 1: Bandwidth is 25.

Submission¶

To submit your work, follow the same procedure you used for Reading 01:

$ cd path/to/cse-34872-su21-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge21               # Create and checkout challenge21 branch

$ $EDITOR challenge21/program.py            # Edit your code

$ git add challenge21/program.py            # Stage your changes
$ git commit -m "challenge21: done"         # Commit your changes

$ git push -u origin challenge21            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge21 program.py ...
  Result Success
    Time 0.06
   Score 6.00 / 6.00

$ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-34872-su21/challenge21
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}