|
|
Problema E - Quick Answers |
Autor: Margarida Mamede (Universidade Nova de Lisboa)
Tipo de problema: Grafos, Fluxo Máximo
Número de ficheiros de teste: 12
Neste problema tínhamos um grafo não dirigido como input e era pedido que descobrissemos se a destruição de D estradas (arestas do grafo) podia significar que dois nós dados A e B passariam a estar "disconexos", ou seja, que podia deixar de haver um caminho possível entre A e B.
A primeira coisa a notar é que isto é a mesma coisa que perguntar se existe maneira de, cortando D estradas, "desligar" os dois nós. Dito de outro modo, queremos destruir "algo" em todos os caminhos possíveis entre A e B.
Pensando no que foi dito no parágrafo anterior, precisamos de saber todos os caminhos entre A e B. Mais precisamente, precisamos de saber caminhos que não partilhem arestas. Se partilharem alguma aresta, para "destruir" estes caminhos basta "destruir" a aresta partilhada.
O problema pode agora ser reduzido a descobrir quantos caminhos sem arestas comuns existem entre A e B. Ora, esta é precisamente uma das aplicações clássicas da descoberta do fluxo máximo entre dois pontos!
Consideremos que a capacidade de cada aresta é 1. Isto garante-nos que apenas passa um caminho nessa aresta. O fluxo máximo entre dois pontos do grafo neste caso passa a indicar precisamente o número de caminhos "edge-independent" entre os dois pontos.
Com tudo isto, resolver o problema passa a ser aplicar um algoritmo de fluxo máximo, um dos algoritmos que até é comum as equipas trazerem nos seus apontamentes. Tendo em conta os limites dados, quase qualquer implementação passaria, como por exemplo um simples Ford-Flukerson. É verdade que poderiamos fazer ainda melhor, aproveitando o facto de o grafo ser não dirigido e a capacidade de cada aresta ser igual a um, mas uma implementação de fluxo máximo "by the book" bastava para ter o problema aceite.
Ligações interessantes: