Pelo texto do problema, estou supondo que a origem é este site:
http://br.spoj.com/problems/ANTS10/
Conforme os comentários:
do @gabriel:
trata-se de um problema que envolve a teoria dos grafos
e do @eric-silva:
Me parece o problema do cacheiro viajante, um problema de otimização np-dificil (ou TSP -
Travelling Salesman
Problem em
inglês).
Sim, é um problema de grafos, mas, apesar de "parecer", este problema não é NP-difícil e também não é NP, pois no enunciado, o autor especifica que ele tem solução (é decidível):
este túnel foi suficiente para permitir que qualquer formiga fosse a
qualquer formigueiro previamente construído...
e não há restrição de direção nos túneis (não é um grafo direcionado).
Na verdade, a primeira vista, parece tratar-se de um problema Árvore de Extensão Mínima, que pode ser resolvido em tempo polinomial (P).
Explicando de forma bem simples e informal, os problemas computacionais são dividos em classes.
Para maiores referências:
https://pt.wikipedia.org/wiki/Complexidade_computacional
As três classes mencionadas aqui são:
P ==> Pode ser resolvido em tempo polinomial
NP ==> Não podem ser resolvidos em tempo polinomial (mas podem ser verificados em tempo polinomial)
NP-difícil ==> São problemas equivalentes aos mais difíceis problemas
em NP e, eventualmente, podem nem ter solução
Exemplos de variação de tempo conforme o tamanho da entrada:
Dada uma entrada de N elementos:
Um problema P com uma complexidade O(N^2)
(para cada elemento acrescentado à entrada, o tempo aumenta ao quadrado):
N=2 -> demora 4 segundos
N=20 -> demora 400 segundos
N=200 -> demora 40.000 segundos
Um problema NP com complexidade O(2^N)
(para cada elemento acrescentado à entrada, o tempo aumenta 2 elevado à entrada):
N=2 -> demora 4 segundos
N=20 -> demora 1.048.576 segundos
N=200 -> demora 1.606.938.044.258.990.275.541.962.092.341.162.602.522.202.993.782.792.835.301.376 segundos
Os exemplos acima são fictícios e não tem nenhuma relação com o problema tratado aqui.
O problema "Árvore de Extensão Mínima" é importante e tem utilidade prática, por exemplo, no cálculo da melhor rota em um GPS ou, ao comprar uma passagem aérea, encontrar melhor rota entre a origem e o destino.
Análise
Cada formigueiro é interligado por um túnel e existe um custo para percorrê-lo.
Existe sempre, no mínimo 1 caminho de um formigueiro para outro.
O custo total para navegar de um formigueiro para outro é a soma dos custos de
cada túnel percorrido.
Entrada
Conforme o site mencionado no início da resposta, estou supondo que os dados serão lidos a partir de um arquivo e não digitados pelo usuário, portanto, a função scanf
pode não ser a ideal neste caso.
Formato do arquivo de entrada (extraído do site do início da resposta):
6 <=== Número de formigueiros = 6
0 8 <=== Linha 1: túnel do formigueiro F1 até F0, com custo 8
1 7 <=== Linha 2: túnel do formigueiro F2 até F1, com custo 7
1 9 <=== Linha 3: túnel do formigueiro F3 até F1, com custo 9
0 3 <=== Linha 4: túnel do formigueiro F4 até F0, com custo 3
4 2 <=== Linha 5: túnel do formigueiro F5 até F4, com custo 2
4 <=== Número de consultas = 4
2 3 <=== Consulta caminho de F2 a F3
5 2 <=== Consulta caminho de F5 a F2
1 4 <=== Consulta caminho de F1 a F4
0 3 <=== Consulta caminho de F0 a F3
2 <=== Número de consultas = 2
0 1 <=== Consulta caminho de F0 a F1
2 <=== Número de consultas = 2
1 0 <=== Consulta caminho de F1 a F0
0 1 <=== Consulta caminho de F0 a F1
6 <=== Número de consultas = 6
0 1000000000 <=== Consulta caminho de F0 a F1000000000
1 1000000000 <=== Consulta caminho de F1 a F1000000000
2 1000000000 <=== Consulta caminho de F2 a F1000000000
3 1000000000 <=== Consulta caminho de F3 a F1000000000
4 1000000000 <=== Consulta caminho de F4 a F1000000000
1 <=== Número de consultas = 1
5 0 <=== Consulta caminho de F5 a F0
0 <=== Fim do arquivo
Estrutura de Dados para Armazenamento
Duas possibilidades a serem utilizadas para armazenar o grafo são:
1) Matriz de adjacência
2) Lista de adjacência
Algoritmos
Existem vários algoritmos conhecidos para tratar o problema "Árvore de Extensão Mínima", entre eles:
Borůvka's algorithm (desenvolvido em 1926)
https://pt.wikipedia.org/wiki/Algoritmo_de_Bor%C5%AFvka)
Algoritmo de Dijkstra
https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra
Algoritmo de Prim
https://pt.wikipedia.org/wiki/Algoritmo_de_Prim
Algoritmo de Kruskal
https://pt.wikipedia.org/wiki/Algoritmo_de_Kruskal
Saída
O custo do menor caminho entre 2 formigueiros, para cada consulta.
Implementação
Abaixo, segue um exemplo comentado de implementação que não soluciona o problema, mas que encontra o caminho entre os 2 formigueiros apenas para os dados do arquivo do link do início da resposta.
Percorrer um grafo para encontrar o melhor caminho normalmente necessita de estruturas de dados auxiliares como, por exemplo, pilhas ou filas.
No exemplo abaixo, a estrutura utilizada foi uma pilha.
Como se trata de uma maratona ou concurso, optei por demonstrar uma possível implementação somente a título didático, portanto:
ela não está otimizada e, provavelmente, não irá encontrar exatamente o menor caminho para todos os casos possíveis
ela não prevê erros nos dados de entrada
ela não prevê caminhos alternativos nem ciclos
Maratona ou Concurso
Já que é uma maratona, provavelmente o programa será testado das mais diversas formas possíveis para verificar como ele trata erros na leitura dos dados, ou mesmo na lógica desses dados.
Dois exemplos claros disso (extraído do site no início da resposta) são:
a segunda e a quarta consultas indicam que serão feitas 2 e 6 consultas respectivamente, mas só foram colocadas 1 e 5 (consultas).
a quarta consulta pede um caminho para o formigueiro F1000000000
, porém, ele não existe
Também, observando-se atentamente a estrutura de entrada de dados descrita no problema:
Cada uma das linhas seguintes N-1 contém dois inteiros que descrevem
um túnel. Linha i, para 1 ≤ i ≤ N-1, contém Ai e Li, indicando que o
formigueiro i estava conectado diretamente ao formigueiro Ai com um
túnel de comprimento Li (0 ≤ ≤ Ai i-1 e 1 ≤ Li ≤ 109).
- Provavelmente (eu não testei), esse problema pode ser solucionado com uma árvore simples, sem necessidade de se utilizar uma "Árvore de Extensão Mínima".
Segue o exemplo:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Estrutura de controle da pilha
typedef struct tpilha {
int item;
struct tpilha *prev;
} pilha;
// Variável que armazena a pilha
static pilha *inicio_pilha = NULL;
// PUSH - inclui um elemento na pilha
void push(int elemento)
{
pilha *temp;
// Cria um elemento temporário
temp = (pilha *) malloc(sizeof(pilha));
temp->item = elemento;
temp->prev = NULL;
if (inicio_pilha == NULL) {
// Define como início da pilha se esta estiver vazia
inicio_pilha = temp;
} else {
// Inclui um elemento no topo da pilha
temp->prev = inicio_pilha;
inicio_pilha = temp;
}
return;
}
// POP - Retira um elemento da pilha ou dá erro, caso a pilha esteja vazia
int pop()
{
pilha *temp;
int ret;
if (inicio_pilha == NULL) {
perror("Erro fatal: pilha vazia.");
exit(1);
} else {
temp = inicio_pilha;
ret = temp->item;
inicio_pilha = inicio_pilha->prev;
free(temp);
}
return ret;
}
// Verifica se a pilha está vazia
int pilhavazia()
{
return (inicio_pilha == NULL ? 1 : 0);
}
// Encontra um caminho entre os parâmetros inicio e fim
int encontra_caminho(size_t tamanho, int **f, int inicio, int fim)
{
int i, j;
int custo[tamanho];
int visitados[tamanho];
int contador = 0;
int elemento_atual;
int custo_atual = 0;
int elemento_ja_visitado;
// Inicializa os vetores
for (i=0; i<tamanho; i++) {
custo[i] = INT_MAX;
visitados[i] = -1;
};
// Empilha um custo inicial 0 e o formigueiro de início
push(custo_atual);
push(inicio);
// Looping de busca
for(;;) {
// se a pilha estiver vazia, é porque já terminou
if (pilhavazia())
break;
// Obtém o elemento atual e o custo atual
elemento_atual = pop();
custo_atual = pop();
// Acrescenta o elemento no vetor de elementos já visitados
visitados[contador++] = elemento_atual;
// Percorre todos os caminhos possíveis a partir do formigueiro_atual
for (i=0; i<tamanho; i++) {
// Verifica se o formigueiro atual já foi visitado
elemento_ja_visitado = 0;
for (j=0; j<contador; j++)
if (visitados[j] == i) {
elemento_ja_visitado = 1;
break;
};
// Pula para o próximo elemento, caso já tenha sido visitado
if (elemento_ja_visitado)
continue;
// Se o formigueiro 'i' não é o próprio formigueiro atual
if (i != elemento_atual) {
// Verifica se existe um caminho do formigueiro atual para o 'i'
if (f[elemento_atual][i] > 0) {
// Acrescenta (soma) o custo atual ao custo deste (this) caminho
if (custo[i] == INT_MAX) {
custo[i] = custo_atual + f[elemento_atual][i];
} else {
1;
/*
Aqui, deve se colocar a rotina para atualizar o custo
somente se ele for menor que o atual.
Não está implementado!
*/
}
// Empilha o custo atual e o caminho encontrado
push(custo[i]);
push(i);
};
}; /*else {
custo[elemento_atual] = 0;
}*/
};
};
printf("Custo do caminho de F%d para F%d: %d\n", inicio, fim, custo[fim]);
return 0;
}
int main(int argc, char **argv)
{
int **formigueiros;
int numero_formigueiros;
int formigueiro_aterior, distancia;
int i, j;
int contador;
FILE *arquivo;
// Abre o arquivo com os dados
arquivo = fopen("formigueiros.txt","r");
if (arquivo == NULL) {
perror("Erro de arquivo.");
exit(2);
};
// Lê o número de formigueiros
fscanf(arquivo, "%d", &numero_formigueiros);
printf("Numero de formigueiros: %d\n", numero_formigueiros);
// Aloca e inicializa a matriz de adjacência com caminhos "nulos", com valor -1
formigueiros = (int **) malloc(numero_formigueiros*sizeof(int *));
for (i=0; i<numero_formigueiros; i++) {
formigueiros[i] = (int *) malloc(numero_formigueiros*sizeof(int *));
for (j=0; j<numero_formigueiros; j++)
formigueiros[i][j] = -1;
}
// Lê os dados dos túneis
contador = 1;
for (i=0; i<(numero_formigueiros-1); i++) {
fscanf(arquivo, "%d %d", &formigueiro_aterior, &distancia);
printf("Tunel de F%d para F%d com distancia %d\n", contador, formigueiro_aterior, distancia);
formigueiros[formigueiro_aterior][contador] = distancia;
formigueiros[contador][formigueiro_aterior] = distancia;
contador++;
}
fclose(arquivo);
printf("\n");
// Imprime a Matriz de adjacência
printf("Matrix de adjacencia lida:\n");
for (i=0; i<numero_formigueiros; i++) {
for (j=0; j<numero_formigueiros; j++)
printf("%d ", formigueiros[i][j]);
printf("\n");
};
printf("\n");
// Encontra caminhos
// Aqui, as consultas estão 'hardcoded', mas no concurso,
// elas devem ser lidas do arquivo
encontra_caminho(numero_formigueiros, formigueiros, 2, 3);
encontra_caminho(numero_formigueiros, formigueiros, 5, 2);
encontra_caminho(numero_formigueiros, formigueiros, 1, 4);
encontra_caminho(numero_formigueiros, formigueiros, 0, 3);
encontra_caminho(numero_formigueiros, formigueiros, 0, 1);
encontra_caminho(numero_formigueiros, formigueiros, 1, 0);
// Libera a memória alocada
for (i=0; i<numero_formigueiros; i++)
free(formigueiros[i]);
free(formigueiros);
// Aguarda o pressionamento de uma tecla para finalizar
getchar();
return 0;
}
O programa foi compilado com TDM-GCC, versão: gcc version 5.1.0 (tdm64-1)
.
O arquivo txt formigueiros.txt
contendo os dados foi colocado no mesmo diretório do arquivo executável.
Após a execução, a saída do programa é a seguinte:
Numero de formigueiros: 6
Tunel de F1 para F0 com distancia 8
Tunel de F2 para F1 com distancia 7
Tunel de F3 para F1 com distancia 9
Tunel de F4 para F0 com distancia 3
Tunel de F5 para F4 com distancia 2
Matrix de adjacencia lida:
-1 8 -1 -1 3 -1
8 -1 7 9 -1 -1
-1 7 -1 -1 -1 -1
-1 9 -1 -1 -1 -1
3 -1 -1 -1 -1 2
-1 -1 -1 -1 2 -1
Custo do caminho de F2 para F3: 16
Custo do caminho de F5 para F2: 20
Custo do caminho de F1 para F4: 11
Custo do caminho de F0 para F3: 17
Custo do caminho de F0 para F1: 8
Custo do caminho de F1 para F0: 8
Apenas para complementar:
Segue abaixo um link para um vídeo que explica sobre o algoritmo de Dijkstra.
Apesar do vídeo estar em inglês, dá para acompanhar o algoritmo apenas pelas imagens:
https://www.youtube.com/watch?v=BQMjTSafmKk