Problema general: dado un grafo especificado en un archivo, su programa listara la red de flujo máxima para ir desde el nodo 0 al último N-1.
La especificación del grafo se encuentra en un archivo que se
especifica en la línea de comandos de su programa. Un ejemplo
de ejecución es:
%rfm graph.txt
Formato de entrada
El formato del archivo de entrada es:
{<numero entero> <numero entero> <capacidad>CR}+
Es decir cada línea un arco del grafo representado por dos
números enteros. Los vértices son números enteros
de 0 a N-1. 0 es la fuente y N-1 el resumidero. La capacidad de cada
arco es un número real en el intervalo abierto (0 , 1.0)
Se asume que el archivo está bien creado de modo, por ejemplo
que no hay saltos en los números de vértices usados y
que el grafo es conexo.
Para probar su programa haga uso del siguiente archivo graph.txt . Su tarea será revisada con otro grafo de prueba además de éste.
Formato de salida
La salida de su programa debe mostrar líneas del tipo
{<número nodo> <número nodo>
<flujo>/<capacidad> CR}+
para cada arco del grafo.
Para que usted desarrolle esta tarea se recomienda:
1.- Hacer una función que implemente BSF para obtener el camino
de aumento. Este programa toma como entrada el grafo, y genera como
salida el camino de aumento desde resumidero a fuente.
2.- Representar el grafo usando dos matrices: en una se ubican las
capacidades y en otra los flujos.