Java

Fundação CECIERJ - Vice Presidência de Educação Superior a Distância

Curso de Tecnologia em Sistemas de Computação
AD2 de Programação III
2° semestre de 2014
Nome:
Matrícula:
Pólo:
Exercício (ENTREGAR OS ARQUIVOS EM MÍDIA, PARA FINS DE TESTE,
JUNTAMENTE COM A AD IMPRESSA):
Considere que sua empresa seja contratada por uma outra companhia para resolver o problema de projeto de redes a 2-caminhos. Este problema consiste em realizar ligações de vários pares de dispositivos eletrônicos usando OU uma ligação direta,
OU um outro dispositivo eletrônico entre este par, MINIMIZANDO o custo total destas ligações. Uma maneira de resolver este problema é, a partir de cada par de dispositivos, descobrir qual é a ligação mais barata possível. Neste momento, o custo das ligações que já fazem parte da solução passam a ser zero, indicando que esta ligação pode ser usada para ligar mais de um par de dispositivos.
Seu programa deve receber, como parâmetro de entrada, um arquivo contendo as ligações possíveis e os custos associados a essas ligações, e um outro arquivo de entrada indicando os pares que devem ser ligados OBRIGATORIAMENTE. Seu programa deve retornar um arquivo contendo as ligações usadas e o custo da solução. Um EXEMPLO dos arquivos de entrada neste formato seriam (OBSERVE QUE
SEU PROGRAMA DEVE FUNCIONAR PARA QUAISQUER ARQUIVOS NOS FORMATOS
ANTERIORMENTE DEFINIDOS):
//ARQUIVO DE LIGAÇÕES POSSÍVEIS
4
//NÚMERO DE DISPOSITIVOS
1 2 3
//O DISPOSITIVO 1 LIGA-SE AO DISPOSITIVO 2 COM CUSTO 3
1 3 1
1 4 2
2 3 1
2 4 3
3 4 3
//ARQUIVOS DE LIGAÇÕES QUE DEVEM SER FEITAS PELO SEU SOFTWARE
2
//NÚMERO DE LIGAÇÕES OBRIGATÓRIAS
1 2
//SEU SOFTWARE DEVE LIGAR O DIPOSITIVO 1 AO 2
3 4
Logo após a leitura, a solução deve ser calculada e gravada no arquivo resp.txt.
Para o exemplo acima, o arquivo de resposta seria composto das ligações {1-3,
2-3, 1-4} com custo 4. Neste caso, a ligação 1-3 foi usada duas vezes. Por questões de desempenho, seu