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 G(V, E) que continen n nodos y m aristas, en donde cada arista (u, v) \in E tiene una capacidad no negativa c(u, v) \ge 0. 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: n \le 10^2 y m \le 10^3

50% de los casos: n \le 10^3 y m \le 10^4

100% de los casos: n \le 10^4 y m \le 10^5

Entrada

La primera línea contiene dos enteros n y m, representando la cantidad de nodos y de aristas respectivamente.

Las siguientes m líneas contienen tres enteros u, v y c, representado cada línea una arista que va desde el nodo u al nodo v con una capacidad de c 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


  • 0
    Ali  commented on March 20, 2023, 7:15 p.m.

    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


  • 1
    humbertoyusta  commented on July 13, 2020, 5:00 p.m.

    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?


    • 1
      ToOma_KFP  commented on July 13, 2020, 9:10 p.m.

      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.


  • 1
    josue  commented on March 25, 2020, 1:19 p.m.

    cual es el limite superior de c?