OIT needs your help. eduroam is having some problems 1 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 2. 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.

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.
```

Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(VE^2)`, where `V` is the number of vertices and `E` is the number of edges in the graph. Space Complexity `O(V+E)`, where `V` is the number of vertices and `E` is the number of edges in the graph.

Your solution may be below the targets, but it should not exceed them.

Programming Challanges¶

This is based on 820 - Internet Bandwidth problem on the UVa Online Judge.

Submission¶

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

```\$ cd path/to/cse-30872-fa21-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 challenge20               # Create and checkout challenge20 branch

\$ \$EDITOR challenge20/program.py            # Edit your code

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

\$ git push -u origin challenge20            # Send changes to GitHub
```

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

```\$ .scripts/check.py
Checking challenge20 program.py ...
Result Success
Time 0.06
Score 6.00 / 6.00

\$ curl -F source=@challenge20/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge20
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}
```

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 10 TA List.

1. Quelle surprise.

2. We can only wish.