ECS 60 Homework 3: Operation Miraq Reconstruction

"Mission Accomplished". George W. Bush, May 1, 2003.

Due: Wednesday, May 13 at 2200 hours.

Hand out: sample input, my reference program

Hand in:

• Makefile and all the necessary program files. When I type "make" with no command line argument, your Makefile should create an executable named spantree. Your program should compile on CSIF Linux machines and have the same input/output behavior as my reference program.
• readme.pdf: a PDF file briefly
  • describing your algorithms. You may use succinct pseudo code if you like.
  • stating and justifying the running time of your algorithms.

Note: This is a group homework. You should work in groups of two. Only one person from each group shall hand in all the files.
On the first two lines of Makefile, write each team member's email username at ucdavis.edu, last name, and first name (one person per line) as comments. For example:
# bsimpson; Simpson, Bart
# mburns; Burns, Montgomery
If you fail to follow this specification, you will lose points.

Description

A long time ago in a galaxy far, far away, the country Miraq had n cities and m old roads, where each road connected a pair of cities. Due to the treacherous mountains, there was no road or even path between some cities (i.e., some cities were unreachable from others). During Operation Miraq Freedom, which spread democracy across Miraq like wildfire in summer Southern California, the Mamerican forces evaporated all the old roads in Miraq. As the Commanding General of the Mamerican forces, you are in charge of Operation Miraq Reconstruction, which will build new roads in Miraq subject to the following constraints:

• Due to the treacherous mountains, you may build new roads only between the cities where old roads existed before Operation Miraq Freedom.
• You should build enough new roads such that if City A was reachable from City B via some old roads, City A must be reachable from City B via some new roads.
• You should minimize the total lengths of the new roads to be built.

Define a region to be a set of cities that will be reachable from one another via some new roads. For each region, you will select as the capital the city that minimizes the maximum distance (via new roads) from any city (in the region) to the capital.

Find the algorithms of the best asymptotic running times.

You may NOT use STL classes except the string class.

Input: Read input from cin. The input contains the number of cities (n), the number of old roads, and a series of old roads where each road consists of its two terminal cities and its distance. Each city is represented by a unique integer from 0 to n-1. Each distance is represented by an integer. Here is an example input.

You need not handle errors in input.

Output:

• One the first line, print the number of regions. For example:
  Number of regions: 2
• Print each region in the ascending order of the number of cities in the region. For each region:
  • On the first line, print:
    Region
  • On the second line, print the capital represented by its number. For example:
    Capital: 3
  • On the third line, print the maximum distance from any city in the region to the capital. For example:
    Maximum distance: 57
  • Then, print each new road per line in the ascending order of the distances of the roads. For each new road, print its two terminal cities represented by their numbers (print the smaller number before the larger number), and then the length of the road. For example:
    0 5 10
• The output of your program must match the output of my reference program. In other words, if you run
  diff my_output your_output
  you should see no output from diff

Hints: You probably need to implement union-find, an O(n log n) sorting, min heap, minimum cost spanning tree, Adjacency Multilist representation of graphs (Section 6.1.3.3 in the textbook). You will also need to invent an algorithm not in the textbook.

Trivia: For the etymology of the city and country names in this story, watch 2007 Mypods and Boomsticks.