Encerrado

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 *[url removed, login to view]*. 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 *[url removed, login to view]*. 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

Habilidades: Programação C, Engenharia, Linux, MySQL, PHP, Arquitetura de software, Teste de Software

Ver mais: why graph, vertices graph, vertex programming software, tree programming, programming tree, programming graph, programming degree, problem graph, integers form, graph problem, graph programming, graph edge, graph tree, free data input software, finding integers, edge graph, degree tree, programming find output, tree graph, algo data, than vi, integer programming, incident, free graph, c algo

Acerca do Empregador:
( 0 comentários ) Turkey

ID do Projeto: #3064797

9 freelancers estão ofertando em média $40 para este trabalho

mihaiscortaru

See private message.

$24.57 USD in 3 dias
(158 Comentários)
6.0
DanD

See private message.

$34 USD in 3 dias
(209 Comentários)
5.8
utopiaprogr

See private message.

$63.75 USD in 3 dias
(61 Comentários)
5.4
thecoder256

See private message.

$34 USD in 3 dias
(33 Comentários)
4.6
zdcodinginc

See private message.

$55.25 USD in 3 dias
(24 Comentários)
4.5
obisoft

See private message.

$85 USD in 3 dias
(6 Comentários)
3.7
rebuildingteam

See private message.

$25.5 USD in 3 dias
(20 Comentários)
3.5
paulabramsvw

See private message.

$21.25 USD in 3 dias
(6 Comentários)
2.9
dbontchev

See private message.

$12.75 USD in 3 dias
(0 Comentários)
0.0