# Aplicaciones de Flujos

## Maximum bipartite matching

Dado un grafo bipartito, hallar la mayor cantidad de aristas tal que cada nodo sea adyacente a lo más a una de las aristas seleccionadas.

### Solución

1. Añadir arista de capacidad $1$ desde $s$ a cada nodo del lado izquierdo.
2. Añadir arista de capacidad $1$ desde cada nodo del lado derecho a $t$.
3. Añadir las aristas originales desde el lado izquierdo al lado derecho con capacidad $1$.
4. El tamaño del flujo máximo es igual al emparejamiento bipartito máximo.

### Reconstrucción de las respuestas

1. Buscar las aristas que van del lado izquierdo al lado derecho y que tengan flujo $1$.

### Problema de practica

- https://codeforces.com/problemset/problem/1139/E

## Generalización del maximum bipartite matching
Dado un grafo bipartito, seleccionar la mayor cantidad de aristas cumpliendo las siguientes restricciones

- Cada arista $(l_i,r_i)$ puede ser seleccionada a lo más $a_i$ veces.
- Cada nodo $l$ del lado izquierdo puede ser adyacente de a lo más $b_l$ aristas seleccionadas.
- Cada nodo $r$ del lado derecho puede ser adyacente de a lo más $c_r$ aristas seleccionadas.

### Solución

- Una arista dirigida de $l_i$ a $r_i$ con capacidad $a_i$ para cada arista $(l_i,r_i)$ del bipartito original.
- Una arista dirigida de $s$ a cada nodo del lado izquierd con capacidad $b_l$.
- Una arista dirigida de cada nodo del lado derecho a $t$ con capacidad $c_r$.
- El emparejamiento máximo es igual al flujo máximo.

### Recostrucción de la respuesta

- Para cada arista del grafo original, la cantidad de flujo que pasa por ella es la cantidad de veces que fue seleccionada.

### Problema de practica
- https://codeforces.com/contest/512/problem/C

## Cobertura mínima de nodos

Dado un grafo bipartito, hallar la minima cantidad de nodos que hay que tomar para que cada arista sea adyacenta a lo menos a un nodo seleccionado.

### Solución ([Teorema de Köning](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)))

1. Hallar el máximo emparejamiento bipartito.
2. La cobertura mínima de vertices es igual al máximo emparejamiento bipartito.

### Reconstrucción de la respuesta

1. Realizar una dfs desde $s$ en la red residual utilizando sólo aristas no saturadas (con flujo menor a la capacidad).
2. Los nodos del lado izquierdo **no** visitados y los nodos del lado derecho **sí** visitados son el cubrimiento de vértices mínimo.

### Problema de ejemplo

-https://codeforces.com/group/Ohoz9kAFjS/contest/266572/problem/D

-[Heavy Chain Clusterization](https://codeforces.com/gym/100269/problem/H)

## Conjunto independiente máximo

Hallar el máximo conjunto de nodos que pueden ser seleccionados, tal que ningún par de los nodos seleccionados sea adyacente.

### Solución

1. Hallar el máximo emparejamiento bipartito.
2. La respuesta es la cantidad de nodos menos el máximo emparejamiento bipartito.

### Reconstrucción de la respuesta
1. Realizar una dfs desde $s$ en la red residual utilizando sólo aristas no saturadas (con flujo menor a la capacidad).
2. Los nodos del lado izquierdo **sí** visitados y los nodos del lado derecho **no** visitados son el conjunto independiente máximo.

### Problema de práctica
- [Easter Eggs](https://codeforces.com/gym/101666/problem/E)

## Corte mínimo

Dado un grafo con peso en las aristas, eliminiar un conjunto de aristas cuyo peso total sea mínimo con la finalidad de desconectar dos nodos dados $s$ y $t$.

### Solución ([Teorema Max-flow Min-cut](https://brilliant.org/wiki/max-flow-min-cut-algorithm/#:~:text=The%20max%2Dflow%20min%2Dcut,the%20source%20from%20the%20sink.))

1. Crear una red de flujo donde el peso de cada arista sea la capacidad.
2. El corte mínimo es igual al flujo máximo en esta red.

### Reconstrucción de la respuesta
1. Realizar una dfs en la red residual, yendo sólo por aristas no saturadas.
2. Las aristas saturadas que van de un nodo visitado a uno no visitado son las que se cortan.

### Problemas de práctica
- https://codeforces.com/group/Ohoz9kAFjS/contest/266572/problem/C

## Partición de elementos en dos conjuntos

Se tienen elementos que se quieren particionar en dos conjuntos $S$ y $T$. Se podrían tener los siguientes costos, donde cada uno es opcional:

- Cuesta $b_i$ colocar el elemento $i$ en el conjunto $S$.
- Cuesta $a_i$ colocar el elemento $i$ en el conjunto $T$.
- Cuesta $c_{i,j}$ colocar los elementos $i$ y $j$ en conjuntos distintos.
- Cuesta $d_{i,j}$ colocar al elemento $i$ en $S$ y al mismo tiempo al elemento $j$ en $T$.

### Solución
1. Crear una red de flujo con un nodo para cada elemento.
2. Añadir arsita dirigida de $S$ a cada nodo con capacidad $a_i$.
3. Añadir arista dirigida de cada nodo a $T$ con capacidad $b_i$.
4. Añadir arista bidireccional entre $i$ y $j$ con capacidad $c_{i,j}$.
5. Añadir arista dirigida de $i$ a $j$ con capacidad $d_{i,j}$.
6. El costo mínimo es el flujo máximo en esta red.

### Reconstrucción de la respuesta
1. Realizar una dfs en la red residual, yendo sólo por aristas no saturadas.
2. Los nodos **sí** visitados se colocan en el conjunto $S$, y los **no** visitados en el conjunto $T$.

### Problemas de práctica
- https://www.spoj.com/problems/COCONUTS/

## Selección de proyectos (project selection)
Se te dan $n$ propuestas de proyectos, donde el proyecto $i$ te da un beneficio de $a_i$, y $m$ máquinas, donde la máquina $j$ cuesta $b_i$. Para cada proyecto, se te da la lista de máquinas necesarias. Cada máquina sólo necesita ser comparada a lo más una vez y puede ser usada en cualquier cantidad de proyectos.

### Solución
1. Crear una red de flujo bipartita Los nodos del lado izquierdo representan los proyectos, y los nodos del lados derecho las máquinas.
2. Colocar arista de $s$ a cada proyecto con capacidad $a_i$.
3. Colocar arista de cada proyecto a cada máquina de la que depende con capacidad infinita.
4. Colocar arista de cada máquina a $t$ con capacidad $b_i$.
5. La respuesta es la suma de los beneficios de los proyectos menos el flujo máximo.

### Reconstrucción de la respuesta
1. Realizar una dfs en la red residual, yendo sólo por aristas no saturadas.
2. Los proyectos y máquinas visitados se eligen.

### Problemas de práctica
- https://codeforces.com/contest/1082/problem/G

## Ploblema de la clausura (closure problem)
Dado un grafo dirigido con pesos en los nodos (los pesos pueden ser positivos o negativos), seleccionar un subconjunto con peso máximo, con la restricción de que si hay una arista dirigida de $u$ a $v$ y se selecciona el nodo $u$, también se debe seleccionar el nodo $v$.

### Solución

1. Colocar arista de $s$ a cada nodo positivo con capacidad igual al valor del nodo.
2. Colocar las aristas originales con capacidad infinita.
3. Colocar arista de cada nodo negativo a $t$ con capacidad igual al valor absoluto del valor del nodo.
4. La respuesta es la suma de los valores de los nodos positivos menos el flujo máximo.

### Reconstrucción de la respuesta
1. Realizar una dfs en la red residual, yendo sólo por aristas no saturadas.
2. Los nodos visitados se eligen.

### Problemas de práctica

- https://codeforces.com/gym/105873/problem/K

## Problema de la circulación (circulation problema)
Se te da una red de flujos, pero que no tiene los nodos especiales $s$ y $t$. Cada arista tiene una capacidad y una demanda. Se debe encontrar una asignación valida de flujo, tal que el flujo que pasa por cada arista sea mayor o igual a la demanda, y menor o igual a la capacidad. Se debe cumplir la restricción de que, para cada nodo, la suma del flujo que entra es la misma que la suma de flujo que sale.

### Solución
1. Crear una red de flujo modificada con los nodos originales y crear dos nodos $s$ y $t$.
2. Para cada arista $(u,v)$ en el grafo original, cuya demanda es $d_{(u,v)}$ y capacidad es $c_{(u,v)}$, crear tres aristas en la red de flujos:
a. Una arista de $s$ a $v$ con capacidad $d_{(u,v)}$.
b. Una arista de $u$ a $t$ con capacidad $d_{(u,v)}$.
c. Una arista de $u$ a $v$ con capacidad $c_{(u,v)}-d_{(u,v)}$.
3. Hallar el flujo máximo de $s$ a $t$.
4. Existe respuesta si el flujo máximo en la red es igual a la suma de las demandas de todas las aristas.

### Reconstrucción de la respuesta
1. El flujo por la arista $(u,v)$ en la red original es igual a $d_{(u,v)}$ más el flujo que pasa por la arista $(u,v)$ en la red modificada.

### Problemas de práctica

## Flujo con demanda
Se te da una red de flujo (con los nodos $s$ y $t$). Cada arista tiene una capacidad y una demanda. Se debe encontrar una asignación valida de flujo, tal que el flujo que pasa por cada arista sea mayor o igual a la demanda, y menor o igual a la capacidad.

### Solución
1. Se crea una red de flujo modificadas, donde sea crea un nuevo source $s'$ y un nuevo sink $t'$
2. Para cada arista $(u,v)$ en la red original, cuya demanda es $d_{(u,v)}$ y capacidad es $c_{(u,v)}$, crear tres aristas en la red de flujos:
a. Una arista de $s'$ a $v$ con capacidad $d_{(u,v)}$.
b. Una arista de $u$ a $t'$ con capacidad $d_{(u,v)}$.
c. Una arista de $u$ a $v$ con capacidad $c_{(u,v)}-d_{(u,v)}$.
3. Agregar arista de $t$ a $s$ con capacidad infinita.
4. Hallar el flujo máximo de $s'$ a $t'$
5. Existe respuesta si el flujo máximo en la red es igual a la suma de las demandas de todas las aristas.

### Reconstrucción de la respuesta
1. El flujo por la arista $(u,v)$ en la red original es igual a $d_{(u,v)}$ más el flujo que pasa por la arista $(u,v)$ en la red modificada.
2. El flujo de $s$ a $t$ en la red original es igual al flujo de la arista de $t$ a $s$ en la red modificada.

### Problemas de práctica
- https://codeforces.com/problemset/problem/2046/D (+ flujo con costo mínimo)

## Flujo máximo con demanda
Se te da una red de flujo (con los nodos $s$ y $t$). Cada arista tiene una capacidad y una demanda. Se debe hallar el flujo **máximo** de $s$ a $t$, tal que el flujo que pasa por cada arista sea mayor o igual a la demanda, y menor o igual a la capacidad.

### Solución
1. Construir la misma red modificada descrita en la sección "Flujo con demanda".
2. Hacer búsqueda binaria sobre la máxima demanda que se le puede colocar a la arista de $t$ a $s$ en la red modificada para que exista respuesta.
a. Notar que esto implica volver a transformar la red modificada de la forma descrita en la sección "Flujo con demanda".

### Reconstrucción de la respuesta
1. El flujo por la arista $(u,v)$ en la red original es igual a $d_{(u,v)}$ más el flujo que pasa por la arista $(u,v)$ en la red modificada.
2. El flujo de $s$ a $t$ en la red original se obtiene por medio de la búsqueda binaria.

### Problemas de práctica

## Flujo mínimo con demanda
Se te da una red de flujo (con los nodos $s$ y $t$). Cada arista tiene una capacidad y una demanda. Se debe hallar el flujo **mínimo** de $s$ a $t$, tal que el flujo que pasa por cada arista sea mayor o igual a la demanda, y menor o igual a la capacidad.

### Solución
1. Construir la misma red modificada descrita en la sección "Flujo con demanda".
2. Hacer búsqueda binaria sobre la mínima capacidad que se le puede colocar a la arista de $t$ a $s$ en la red modificada para que exista respuesta.

### Reconstrucción de la respuesta
1. El flujo por la arista $(u,v)$ en la red original es igual a $d_{(u,v)}$ más el flujo que pasa por la arista $(u,v)$ en la red modificada.
2. El flujo de $s$ a $t$ en la red original se obtiene por medio de la búsqueda binaria.

### Problemas de práctica

## Partición de DAG en caminos
Dado un DAG, descomponerlo en la mínima cantidad posible de caminos disjuntos.

### Solución
### Reconstrucción de la respuesta
### Problemas de práctica

## Partición de DAG en cadenas
Dado un DAG, descomponerlo en la mínima cantidad posible de cadenas disjuntas. Una cadena es una secuencia de nodos $u_1,u_2,\dots,u_k$, tal que existe un camino ente $u_i$ y $u_{i+1}$ (para $1\leq i < k$). Notar que no es necesario que $u_i$ y $u_{i+1}$ estén conectadas con una arista.

### Solución
### Reconstrucción de la respuesta
### Problemas de práctica

## Máxima anticadena en un DAG
Dado un DAG, hallar la máxima anticadena. Una anticadena es un conjunto de nodos, tal que entre no existe ningún camino entre ningún par de nodos.

### Solución (Dilworth Theorem)
### Reconstrucción de la respuesta
### Problemas de práctica
- https://codeforces.com/gym/102428/problem/A

## Teorema del Matrimonio de Hall
### Problemas de práctica
- https://codeforces.com/group/XrhoJtxCjm/contest/422717/problem/M

## Flujo máximo con costo mínimo
### Solución
### Reconstrucción de la respuesta
### Problemas de práctica
- https://codeforces.com/problemset/problem/2046/D (+ flujo con demanda)

## Flujo con costo mínimo
### Solución
### Reconstrucción de la respuesta
### Problemas de práctica