Algo hw7

You need to find degree constrained minimum spanning tree (DCMST) . Degree constrained minimum spanning tree of a graph *G* is the minimum spanning tree in *G* in which the degree of no vertex exceeds a given number *d* (*reminder: degree of a vertex is the number of edges incident to it*). Unfortunately, finding DCMST of a given graph is a much harder problem than finding regular MST. (Why? [**hint:** *Take d=2, does that remind you of another very famous problem?*]) **Input** Your program will read the input data from a file named *[login to view URL]*. The first line of the input file contains three integers *n*, *m* and *d* denoting the number of vertices, number of edges and degree constaint respectively. (1< *n* <=25) Vertices are denoted by numbers between 1 and n. Each of the following *m* lines contains three numbers ui, vi and wi (0 < wi <= 1000) which states that vertex ui is connected to vertex vi by an edge of length wi. You can assume that the input is error-free. _deimos.inp_ 5 6 2 1 5 7 5 2 3 3 5 4 3 4 2 2 4 8 1 4 5 **Output** Output of your program is a file named *[login to view URL]*. The first line of the output file must contain a single integer number giving the total distance of the DCMST of the given graph. Each of the following *n*-1 lines must contain two numbers ui and vi, stating that vertex ui is connected to vertex vi in the resulting DCMST. _deimos.out_ 14 3 4 2 5 3 5 4 1 ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site). ## Platform Linux