PKU 2735 - Reliable Nets

Autor da análise: MarchettiMarchetti

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2735

Resumo

Dado um grafo G=(V,E) onde |V|=n e |E|=m e uma função custo $c:E \to N_+$ determinar quando existir o custo c(E') no subgrafo G'=(V,E') de G que é conexo não tem pontes e c(E')<c(E") para todo G"=(V,E") subgrafo de G conexo sem pontes, ou dizer que não existe tal subgrafo.

Solução

Como n e m (principalmente m) são pequenos o problema pode ser resolvido por backtracking sobre os subconjuntos de E.
Uma forma de se fazer isso para cada caso de teste é a seguinte:

  • Testar inicialmente se G é conexo (caso contrário esse caso de teste está resolvido).
  • Dada uma ordem arbitrária das arestas testar manter ou retirar cada aresta sempre verificando se o grafo resultante possui pontes, e se não possuir comparar com o mínimo custo obtido até o momento. Como o teste de pontes é feito a cada retirada de aresta não é possível que o grafo fique não conexo antes de possuir uma ponte e logo esse teste basta.
  • Devolver o mínimo custo encontrado.

Essa solução é O( $2^m * (m+n)$ ) se usado um algoritmo decente para procurar pontes (http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/bridges.html) o que é razoável (Naquelas… Mas dá para passar =) ) já que nos testes temos $n \leq 15$ e $m \leq 20$, ainda mais que é fácil perceber (ainda que difícil de provar) que essa análise é um pouco folgada.
Para ilustrar um pouco:
O número de arestas que podem ser retiradas (e a profundidade máxima na árvore do backtracking) e o grafo continuar biconexo é m' = (min{20,n^2} - n) então na verdade a solução é O( $2^m' * (m+n)$ ), onde m'<=15 (m' é máximo quando n=5).

Um corte interessante no backtracking pode ser feito se mantivermos os graus de cada vértice no grafo de cada passo, pois nunca se pode retirar uma aresta xy que possui ponta em um vértice, digamos o x, de grau 2 já que se isso fosse feito a outra aresta que tem ponta em x se tornaria uma ponte.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License