Challenge 20: 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 has a bandwidth of 20 and node 3 and node 1 has a bandwidth of 10. The total maximum bandwidth between the source (1) and the destination (4) is through the whole network is 25. This because we can send bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4.

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.

Note: All connections are bi-directional, and there may be multiple connections between a pair of nodes (but a node cannot connect to itself).

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 00:

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

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

$ $EDITOR challenge20/program.cpp           # Edit your code

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

$ git push -u origin challenge20            # Send changes to GitLab

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

$ .scripts/submit.py
Submitting challenge20 assignment ...
Submitting challenge20 code ...
  Result Success
   Score 6.00
    Time 0.03

$ curl -F source=@challenge20/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge20
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 10 TA List to determine your corresponding TA for the merge request.