By the text of the problem, I’m guessing the origin is this site:
http://br.spoj.com/problems/ANTS10/
As the comments:
of @Abriel:
is a problem involving graph theory
and @Eric-silva:
It seems to me the traveling cacheiro problem, an np-hard optimization problem (or TSP -
Travelling Salesman
Problem in
english).
Yes, it is a graph problem, but although "it seems", this problem is not NP-hard and also is not NP, because in the statement, the author specifies that he has a solution (it is decidable):
this tunnel was enough to allow any ant to
any previously constructed anthill...
and there is no steering restriction in the tunnels (not a directed graph).
In fact, at first glance, it seems to be a problem Tree of Minimum Extension, that can be solved in polynomial time (P).
Explaining in a very simple and informal way, computational problems are divided into classes.
For further reference:
https://en.wikipedia.org/wiki/Computational_complexity
The three classes mentioned here are:
P ==> Can be solved in polynomial time
NP ==> They cannot be solved in polynomial time (but can be checked in polynomial time)
NP-hard ==> Are problems equivalent to the most difficult problems
in NP and eventually may not even have solution
Examples of time variation depending on the size of the input:
Given an input of N elements:
A problem P complex O(N^2) (for each element added to the input, time increases squared):
N=2 -> demora 4 segundos
N=20 -> demora 400 segundos
N=200 -> demora 40.000 segundos
A problem NP intricate O(2^N) (for each element added to the input, the time increases 2 high to the input):
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
The above examples are fictitious and have no relation to the problem dealt with here.
The problem "Minimum Extension Tree" is important and has practical utility, for example, in calculating the best route in a GPS or, when buying an air ticket, find better route between origin and destination.
Analyzing
Each anthill is interconnected by a tunnel and there is a cost to travel it.
There is always at least 1 path from one ant hill to another.
The total cost of navigating from one anthill to another is the sum of the
each tunnel travelled.
Entree
As the site mentioned at the beginning of the reply, I am assuming that the data will be read from a file and not typed by the user, therefore the function scanf may not be ideal in this case.
Input file format (extracted from response start site):
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
Data Structure for Storage
Two possibilities to use for storing the graph are:
1) Adjacency matrix
2) Adjacency list
Algorithms
There are several known algorithms to handle the "Minimum Extension Tree" problem, among them:
Borůvka’s Algorithm (developed in 1926)
https://en.wikipedia.org/wiki/Borůvka's_algorithm)
Algorithm by Dijkstra
https://en.wikipedia.org/wiki/Dijkstra's_algorithm
Prim’s algorithm
https://en.wikipedia.org/wiki/Prim's_algorithm
Kruskal’s algorithm
https://en.wikipedia.org/wiki/Kruskal's_algorithm
Exit
The cost of the smallest path between 2 anthills, for each query.
Implementation
Below is a commented example of implementation that does not solve the problem, but finds its way between the two anthills only for the response start link file data.
Going through a graph to find the best path usually requires auxiliary data structures, for example, batteries or queues.
In the example below, the structure used was a stack.
As it is a marathon or competition, I chose to demonstrate a possible implementation only on a didactic basis, therefore:
it is not optimized and will probably not find exactly the smallest path for all possible cases
it does not predict errors in the input data
it does not provide for alternative paths or cycles
Marathon or Contest
Since it is a marathon, probably the program will be tested in as many ways as possible to check how it treats errors in reading the data, or even in the logic of this data.
Two clear examples of this (taken from the site at the beginning of the answer) are:
the second and fourth consultations indicate that there will be 2 and 6 consultations respectively, but only 1 and 5 (consultations).
the fourth query asks for a way to the ant hill F1000000000, however, it does not exist
Also, carefully observing the data input structure described in the problem:
Each of the following lines N-1 contains two integers describing
a tunnel. Line i, for 1 i N-1, contains Ai and Li, indicating that the
Anthill i was connected directly to the anthill Ai with a
tunnel length Li (0 Ai i-1 and 1 Li 109).
- Probably (I didn’t test), this problem can be solved with a simple tree, without the need to use a "Minimum Extension Tree".
Follow the example:
#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;
}
The program was compiled with TDM-GCC, version: gcc version 5.1.0 (tdm64-1).
The txt file formigueiros.txt containing the data was placed in the same directory as the executable file.
After execution, the output of the program is as follows:
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
Only to complement:
Below is a link to a video that explains about Dijkstra’s algorithm.
Although the video is in English, you can follow the algorithm only through images:
https://www.youtube.com/watch?v=BQMjTSafmKk
I don’t know how to fix this. I’ve been told that it’s using graph theory, which is using mathematical equations,.
– Gabriel
Seems to me the problem with wanderer, an np-hard optimization problem. Here has an interesting material about.
– Eric Silva