Your program should read input from a text file, and calculate the cost of the

solution generated by your algorithm, that is$,$ the cost of the edges in $xA.$ Your

program does not need to return the actual edges, just print out the total cost

rounded to two decimal places to standard output.

Your code will not be benchmarked or tested for time complexity, but for full

points it must be able to run instances similar to "Graph$10$oo$",$ and each test will

time out after $5$ seconds. Your program will also be tested on hidden test cases.

Figure $2$: Illustrating the graph described in Question $2,$ with $n=4,m=5$ and

$a=2.$ Showing an optimal solution having cost $13.$Consider the following variant of the Minimum Spanning Tree $($MST$)$ problem. We

are given an undirected graph $G=(V,E)$ with $n$ vertices $($numbered from o to

$n-1$ and $m$ edges, a positive $($not necessarily unique$)$ edge cost $c_e$ for each edge

in $E,$ and a subset of edges AsubE $($note that A may contain cycles$).$ Suppose that $E$

represents a set of possible direct fibre links between vertices and A represents the

existing set of direct fibre links between vertices. We would like to find the cheapest

way to connect all the vertices into one connected network.

The abstract problem we are interested in solving is to find a subset xsube$\frac{E}{\frac{?}{?}}A$

of edges of minimum cost such that $(V,xA)$ is connected.

Task: Design an algorithm that solves this problem in $O(mlogn)$ time.

Implement your algorithm $($in Ed$)$ and test it on the following instances: Graph$8,$

Graph$250,$ Graph$1$ooo. Each instance is given in a text file as described in Question

Each graph instance is given in a text file using the following format $($where $a$ is

the number of edges in $A)$:

For example, the following text describes the instance depicted in Fig. $2.$ Note

that the vertices are numbered from o to $n-1.$