Problema de Flujo Máximo
Submit solution
Points:
100 (partial)
Time limit:
1.0s
Java 8
2.0s
Perl
2.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB
Dado un grafo dirigido que continen nodos y aristas, en donde cada arista tiene una capacidad no negativa . Se distinguen dos nodos: la fuente(el nodo 1) y el destino(el nodo n). El objetivo es encontrar el flujo máximo que va desde el nodo fuente hasta el nodo destino.
Restricciones:
20% de los casos: y
50% de los casos: y
100% de los casos: y
Entrada
La primera línea contiene dos enteros y , representando la cantidad de nodos y de aristas respectivamente.
Las siguientes líneas contienen tres enteros , y , representado cada línea una arista que va desde el nodo al nodo con una capacidad de unidades.
Salida
El flujo máximo que va desde la fuente hasta el nodo destino.
Ejemplo de Entrada
4 6
3 4 4
2 4 3
1 4 6
1 2 9
2 3 9
1 3 4
Ejemplo de Salida
13
Comments
En este ejercicio utilizo el algoritmo de Ford-Fulkerson que es la misma complejidad que el de Dinitz, alguien que revise mi código y me diga que podría estar mal
A este problema no le falta o le sobra algo, el flujo sin restricciones en el grafo, se puede hallar bajo estas constantes?, o hay alguna restriccion en el grafo?
Hola Humberto. Este problema lo puse para utilizarlo para evaluar una tarea de la asignatura Modelos de Optimización II. Lo solucione empleando el algoritmo de Dinitz que trabaja en O(n^2*m), lo cual para las restricciones del problema no debería dar en tiempo. Los jd los hice de manera aleatoria y pensando en que los estudiantes que lo resolverían no estarían muy familiarizados con la programación competitiva por ello no los hice muy fuerte, aunque el número de aristas y nodos sea grande, esto hace q la implementación de Dinitz de.
cual es el limite superior de c?