Custom Min Spanning Tree

Árvore mínima personalizada

Descrição

Construir uma árvore de extensão a partir de dados de entrada deve obedecer a essas três regras básicas:

1. O gráfico deve ser uma árvore e conter todos os nós.
2. O gráfico deve conter o número máximo possível de bordas de algum comprimento específico, independentemente do custo associado a essas bordas.
3. A soma total dos comprimentos das arestas do gráfico resultante em relação à primeira e da segunda regra deve ser minimizada.

Imagem 1. Esquemas de possíveis conexões entre nós gráficos. As conexões possíveis são retratadas como bordas. As conexões que podem formar a árvore de extensão desejadas são destacadas em vermelho. Os casos a), b), c) correspondem aos exemplos 1, 2, 3 abaixo. Em alguns casos (por exemplo, nos casos B e C), mais de uma árvore de abrangência pode satisfazer as demandas do problema. No entanto, todas essas árvores em abrangência compartilham o mesmo comprimento total. O caso a) ilustra a importância da regra 3. Existem árvores abrangentes contendo arestas (1, 5) e (5, 4) que satisfazem a regra 2, mas não satisfazem a regra 3, pois o comprimento total de qualquer um deles é de pelo menos 17.

Tarefa

A lista de todas as conexões possíveis entre os nós e os respectivos comprimentos de conexão é fornecida. Calcule o comprimento total de uma árvore de extensão que satisfaz todas as três regras apresentadas na descrição.

Os conjuntos de dados para a tarefa foram criados pelos professores da Universidade Técnica da Tcheca para sujeitar a 'algoritmização avançada'.

Entrada

A primeira linha da entrada consiste em dois números inteiros N e M separados pelo espaço. Valor n é o número de nós. Valor m é o número de conexões possíveis entre pares de nós. Em seguida, existem las M, onde cada linha representa uma conexão possível. A linha contém três números inteiros D1, D2, L separados pelo espaço, o que significa que o comprimento da possível conexão entre os nós D1 e D2 é igual a L. Os detectores são numerados de 1 a N. As conexões possíveis estão listadas em uma ordem aleatória. Possui n ≤ 30000 e m ≤ 300000. Cada comprimento é no máximo 10^9.

Saída

A saída é uma linha que contém o comprimento total mínimo da rede necessária. O resultado não é maior que 2^60.

Exemplo 1

Exemplo 1 Os dados de entrada e a rede resultante estão representados na imagem 1 a).

Exemplo 2

Exemplo 2 Os dados de entrada e a rede resultante estão representados na imagem 1 b).

Exemplo 3

Exemplo 2 Os dados de entrada e a rede resultante estão representados na imagem 1 c).

Solução

A tarefa é implementada em Java usando o algoritmo otimizado da Findia União (explicado aqui). No algoritmo, há uma versão modificada do Hashmap implementada pelos autores Justin Couch, Alex Chaffee e Stephen Colebourne. Este hashmap usa apenas números inteiros primitivos e não objetos inteiros java, o que resultou em melhor desempenho.