Autor da análise: Marchetti
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.
Discuta o problema
O meu algoritmo usa estes mesmos princípios: backtracking e pontes. Eu gero todos os 2^m conjuntos de arestas possíveis e o único prunning que eu uso é cortar subconjuntos com (estritamente) menos de n arestas, isso é óbvio, é ímpossivel ter um grafo biconexo com menos de n arestas.
Acho que a única coisa que vale a pena ser comentada tem a ver com forma como eu implementei o backtracking. A idéia geral também é bem padrão, considerar a bijeção entre cada subconjunto e a representação em binários de [0, 2^m), o jeito padrão de implementar isso seria algo como:
Onde cada posição do vetor booleano bool representa um elemento. Eu fiz um teste com essa implementação, consegui AC com um tempo de 641MS. Uma forma como eu implentei inicialmente foi:
Essa forma não é tão evidente, é um pouco mais enxuta, mas principalmente é MUITO mais rápida, usando essa implementação o tempo caiu para 94MS, acontece que operações bit a bit são muito mais rápidas do que divisões.
Nesse caso, ambas forma conseguem AC, mas em outro problema o tempo limite pode não ser tão assim tão folgado. Acho que isso é uma coisa bastante simples, aplicavel a um número grande de problemas de backtracking e, principalmente, pode significar uma economia de tempo não desprezivel.
Isso pode não ser novidade pra muita gente, pra esses, mal ae por ficar floodando o wiki… :-)
Isso não é flood. É um excelente comentário. =)