In this homework, you are asked to solve problems related to the minimum diameter spanning tree (MDST).
There are 5 operations.
1. Add
2. Delete
3. AC
4. Diameter
5. SOSPD
Add
Add v1 v2 w
Add an edge between v1 and v2 and the weight is w.
p.s. v1 is not always smaller than v2.
If there already exists and edge, update to the new one.
(delete the original one and add the new edge)
For example: Add 0 1 10
Delete
Delete v1 v2
Delete the edge between v1 and v2.
p.s. v1 is not always smaller than v2.
For example: Delete 0 1
AC
Output the absolute center.
Case1: absolute center is on a vertex.
Output the index of the vertex.
If there are many absolute centers on vertices, output the one with the smallest index.
Case2: absolute center is on an edge(i, j), and i < j.
Output i j
If there are many absolute centers on edges, output the first one in lexicographical order.
Case3: If there are many absolute centers on both vertices and edges, output the vertex with the smallest index.
If the graph is not connected, output “Not connected graph”.
Diameter
Output the diameter of minimum diameter spanning tree.
If the graph is not connected, output “Not connected graph”.
SOSPD
Output the sum of shortest path distances from absolute center c to all vertices in graph
If the graph is not connected, output “Not connected graph”.
Note:
There are only Add、Delete、AC operations in testcase 1.
There are only Add、Delete、Diameter operations in testcase 2.
There are only Add、Delete、SOSPD operations in testcase 3.
And testcase 4,5,6 would have all operations.
You are allowed to use STL.
A testcase begins with an integer n, representing the number of vertices.
After the first line, the following lines are operations.
Please note:
1) 1 <= the number of vertices <= 100
2) 1 <= weight <= 100
(weight is integer)
3) the diameter of MDST <= 1000
4) SOSPD <= 10000
According to the operations, and each output is separated by a newline symbol.