Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

REDOTICA - Rede ótica

Os caciques da região de Tutuaçu pretendem integrar suas tribos à chamada “aldeia global”. A primeira providência foi a distribuição de telefones celulares a todos os pajés. Agora, planejam montar uma rede de fibra ótica interligando todas as tabas. Esta empreitada requer que sejam abertas novas picadas na mata, passando por reservas de flora e fauna. Conscientes da necessidade de preservar o máximo possível o meio ambiente, os caciques encomendaram um estudo do impacto ambiental do projeto. Será que você consegue ajudá-los a projetar a rede de fibra ótica?

Tarefa

Vamos denominar uma ligação de fibra ótica entre duas tabas de um ramo de rede. Para possibilitar a comunicação entre todas as tabas é necessário que todas elas estejam interligadas, direta (utilizando um ramo de rede) ou indiretamente (utilizando mais de um ramo). Os caciques conseguiram a informação do impacto ambiental que causará a construção dos ramos. Alguns ramos, no entanto, nem foram considerados no estudo ambiental, pois sua construção é impossível.

Sua tarefa é escrever um programa para determinar quais ramos devem ser construídos, de forma a possibilitar a comunicação entre todas as tabas, causando o menor impacto ambiental possível.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém dois números inteiros positivos N e M que indicam, respectivamente, o número de tabas e o número de ramos de redes possíveis. As tabas são numeradas de 1 a N. As M linhas seguintes contêm três inteiros positivos X, Y e Z, que indicam que o ramo de rede que liga a taba X à taba Y tem impacto ambiental Z. Com os conjuntos de teste dados sempre é possível interligar todas as tabas. O final da entrada é indicado quando N = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir uma lista dos ramos de redes que devem ser construídos. A lista deve ser precedida de uma linha que identifica o conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A lista é composta por uma sequência de ramos a serem construídos, um ramo por linha. Um ramo é descrito por um par de tabas X e Y , com X < Y. Os ramos de rede podem ser listados em qualquer ordem, mas não deve haver repetição. Se houver mais de uma solução possível, imprima apenas uma delas. O final de uma lista de ramos deve ser marcado com uma linha em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
3 3
1 2 10
2 3 10
3 1 10
5 6
1 2 15
1 3 12
2 4 13
2 5 5
3 2 6
3 4 6
0 0

Saída:
Teste 1
1 2
1 3

Teste 2
1 3
2 3
2 5
3 4

Restrições

0 ≤ N ≤ 100 (N = 0 apenas para indicar o fim da entrada)
1 ≤ M ≤ N(N-1)/2
1 ≤ X ≤ 100
1 ≤ Y ≤ 100
1 ≤ Z ≤ 100


Adicionado por:Wanderley Guimarăes
Data:2006-04-19
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Olimpiada Brasileira de Informatica 2000

hide comments
2020-12-12 02:32:58
Esse problema, como a maioria dos problemas de mst tem várias soluções possíveis para cada caso de teste, então mesmo que sua resposta de diferente do caso de teste, ambas podem estar corretas (como a do cara de baixo)
2016-07-12 00:47:40
Teste 1
1 2
2 3

Teste 2
2 5
2 3
3 4
1 3

Mesmo com essas saídas deu ACCEPTED, a saída descrita no problema está errada certo?
2016-04-18 00:34:17 Elsio [UFABC]
Similar: http://br.spoj.com/problems/REUNIAO2/
2015-07-08 02:19:41 Elsio [UFABC]
Buble + Kruskal
Sem pegadinhas :)
2014-01-06 12:36:06 Eduardo Rodrigues Santana
me cadastrei a alguns minutos no site e sou iniciante em Java.
Quanto tempo tenho pra responder as questőes ? e se eu năo responder a tempo perco o meu cadastro neste site ?
2012-12-09 00:16:50 Antonio Ribeiro dos Santos Junior
Vinicius năo está errada, só é uma outra possível resposta:
"Se houver mais de uma soluçăo possível, imprima apenas uma delas."
2012-07-11 17:44:51 Vinicius Coelho [UFG]
a saida do primeiro caso está errada.
o certo é:
1 2
2 3
assim como da segunda tbm está...

Last edit: 2012-07-11 17:45:27
2011-01-27 17:35:13 Matheus Pacheco [UFMG]
Gostaram desse "e seja feliz"
2010-09-28 19:03:56 Murilo Adriano Vasconcelos
Coloca um return 0 no final da funçăo main() e seja feliz =)
2010-07-22 01:35:46 David Kennedy Souza Araújo [PUC-GO]
Estou tendo problemas com NZEC Tempo de execuçăo...
o que isso significa?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.