Problema de Flujo Máximo

Points: 100 (partial)

Time limit: 1.0s

Java 8 2.0s

Perl 2.0s

Memory limit: 256M

Author:

ToOma_KFP

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

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

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

Entrada

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

Las siguientes $m$ ~m~ líneas contienen tres enteros $u$ ~u~, $v$ ~v~ y $c$ ~c~, representado cada línea una arista que va desde el nodo $u$ ~u~ al nodo $v$ ~v~ con una capacidad de $c$ ~c~ unidades.

Salida

El flujo máximo que va desde la fuente hasta el nodo destino.

Ejemplo de Entrada

Ejemplo de Salida

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?