O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto comeca com uma linha contendo o numero "x" de vertices de um grafo. As proximas "x" linhas contem as listas de adjacencias do grafo que devem ser processadas. O primeiro numero de cada uma das "x" linhas e' um inteiro n tal que 1 <= n <= x. Depois seguem-se varios inteiros representando vertices adjacentes ao vertice n. A lista de vertices adjacentes termina com o inteiro 0.
O arquivo de entrada e' terminado por um conjunto de dados comecando com "x = 0". Esse conjunto nao deve ser processado.

Considere que 0 <= x <= 100.

Entrada exemplo:
4
1 2 4 0
2 1 3 0
3 2 4 0
4 3 1 0
5
1 2 4 0
2 1 3 0
3 2 4 0
4 3 1 5 0
5 4 0
0

Arquivo de Saida: quest1.out

Para cada conjunto, voce deve imprimir "x+1" linhas. Na primeira linha,
imprima o numero do conjunto, como mostrado na saida exemplo. Nas proximas "x"
linhas,imprima o grafo resultante ao direcionar as arestas deste grafo de forma
que o grau de entrada de cada vértice no grafo direcionado gerado na saída
seja no máximo 1. Uma linha em branco separa cada conjunto. Imprima o grafo no
mesmo formato do arquivo de entrada, mas sem o '0' (zero) final e sem espacos no
fim das linhas.

Saida exemplo correspondente a entrada acima:
Conjunto #1
1 4
2 1
3 2
4 3

Conjunto #2
1 4
2 1
3 2
4 3 5
5

Obs.:

• Não se esqueçam de desalocar toda a lista de adjacência do grafo entre cada processamento;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.

Arquivo de entrada: quest2.in

O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto comeca com uma linha contendo o numero "x" de vertices de um grafo. As proximas "x" linhas contem as listas de adjacencias do grafo que devem ser processadas. O primeiro numero de cada uma das "x" linhas e' um inteiro n tal que 1 <= n <= x. Depois seguem varios pares de inteiros em que cada par representa, um vertice v adjacente ao vertice
n e o peso da aresta n-v. Apos as "x" linhas do grafo segue uma linha contendo um inteiro k que é um vertice de G. Queremos identificar as arestas que compõem os caminhos mais curtos de k para cada um dos vértices de G. O arquivo de entrada e' terminado por um conjunto de dados comecando com "x = 0". Esse conjunto nao deve ser processado.

Considere que 0 <= x <= 100.

Entrada exemplo:

4
4 3 10  1 5 0
2 1 2   3 4 0
3 2 4   4 10 0
1 2 2   4 5 0
2
4
4 3 20   1 70 0
2 1 100  3 10 0
3 2 10   4 20 0
1 2 100  4 70 0
2
4
4 3 20   1 7 0
2 1 100  3 10 0
3 2 10   4 20 0
1 2 100  4 7 0
2
0

Arquivo de Saida: quest2.out

Para cada conjunto, voce deve imprimir "x" linhas, em que x e' o numero de vertices do grafo correspondente ao conjunto. Na primeira linha, imprima o numero do conjunto, como mostrado na saida exemplo. Nas proximas "x-1" linhas imprima a ultima aresta do caminho de menor custo para cada par de vertices (k,z) como mostrado no exemplo abaixo.
Uma linha em branco separa cada conjunto.

Saida exemplo:

Conjunto #1
2 -> 1: Custo = 2 Aresta = 2-1
2 -> 3: Custo = 4 Aresta = 2-3
2 -> 4: Custo = 7 Aresta = 1-4

Conjunto #2
2 -> 1: Custo = 100 Aresta = 2-1
2 -> 3: Custo = 10 Aresta = 2-3
2 -> 4: Custo = 30 Aresta = 3-4

Conjunto #3
2 -> 1: Custo = 37 Aresta = 4-1
2 -> 3: Custo = 10 Aresta = 2-3
2 -> 4: Custo = 30 Aresta = 3-4

Obs.:

• Não se esqueçam de desalocar toda a lista de adjacência do grafo entre cada processamento;

O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.
 

---


 




==========
Questão 03
==========

Arquivo fonte: quest3.c
Arquivo de entrada: quest3.in
Arquivo de saída: quest3.out


 

O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto comeca com uma linha contendo o numero "x" de vertices de um grafo. As proximas "x" linhas contem as listas de adjacencias do grafo que devem ser processadas. O primeiro numero de cada uma das "x" linhas e' um inteiro n tal que 1 <= n <= x. Depois seguem varios pares de inteiros em que cada par representa, um vertice v adjacente ao vertice n e o peso da aresta n-v(os pesos sao sempre positivos). Queremos identificar as arestas que compõem a arvore geradora de peso minimo deste grafo. O arquivo de entrada e' terminado por um conjunto de dados comecando com "x = 0". Esse conjunto nao deve ser processado.
 

Considere que 0 <= x <= 100.

Entrada exemplo:

3
1 2 5  3 3 0
2 1 5  3 7 0
3 1 3  2 7 0
3
3 2 7 0
2 1 5  3 7 0
1 2 5 0
5
1 2 25  3 30  4 10 0
2 1 25  3 50  5 15 0
3 1 30  2 50  4 40  5 20 0
4 1 10  3 40  5 5 0
5 2 15  3 20  4 5 0
0

Arquivo de Saída: quest3.out

Para cada conjunto, você deve imprimir "x+2" linhas, em que x é o número de vértices do grafo correspondente ao conjunto. Na primeira linha, imprima o némero do conjunto, como mostrado na saída exemplo. Na próxima linha, imprima o peso da árvore encontrada(soma dos pesos de todas as suas arestas). Nas próximas "x" linhas, imprima a nova lista de adjacências do grafo(árvore), sem os custos.
Uma linha em branco separa cada conjunto.

Saída exemplo:

Conjunto #1
Peso: 8
1 2 3
2 1
3 1

Conjunto #2
Peso: 12
1 2
2 1 3
3 2

Conjunto #3
Peso: 50
1 4
2 5
3 5
4 1 5
5 2 3 4

Obs.:

• Não se esqueçam de desalocar toda a lista de adjacência do grafo entre cada processamento;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.
• Só existirá uma única árvore de peso mínimo nas nossas entradas.