¿Asumo que tiene múltiples fuentes y múltiples sumideros donde el flujo sale de cada fuente y cada sumidero recibe flujo?
Sí, pero debe transformarlo en una red de flujo de sumidero único de fuente única antes de usar Ford-Fulkerson. Por definición, una fuente puede enviar tanto flujo como pueda ser empujado a través de la red, y un sumidero puede recibir tanto flujo como puede enviarse a través de la red. Introducir una súper fuente sy una súper sumidera t. Agregue bordes dirigidos desde la super fuente a cada fuente con capacidad [math] \ infty [/ math], luego agregue bordes dirigidos desde cada sumidero al super sumidero, cada uno con capacidad [math] \ infty [/ math]. Técnicamente, puede simplificar [math] \ infty [/ math] simplemente tomando la suma de las capacidades que salen / ingresan a una fuente / sumidero en su lugar (suponiendo que ningún flujo salga del sumidero y que ningún flujo ingrese a una fuente; consulte https: // www.cs.cmu.edu/~ckingsf/… de lo contrario, también se analizan algunas otras extensiones).
- Cómo mejorar en la implementación de algoritmos
- ¿Debo ir a un curso de algoritmos o comenzar a resolver problemas en TopCoder / CodeChef, etc.?
- ¿Cuál es la diferencia entre los algoritmos de programación de tareas y los algoritmos de equilibrio de carga (estáticos y dinámicos)?
- ¿Cuál es la mejor manera de depurar un algoritmo recursivo?
- Cómo estimar pi usando un hexágono unitario en Matlab
Fuente: Introducción a los algoritmos, por Cormen et al.
Para obtener más información, consulte (este es el capítulo en CLRS sobre el tema): http://www.ifp.illinois.edu/~ang… (página 5–6 de este PDF).
Ahora que la red tiene una fuente clara y un sumidero claro, puede encontrar rutas de aumento desde la fuente única al sumidero (algo que hace Ford-Fulkerson).
¡Espero que esto ayude!
