Una red de flujo es un gráfico dirigido G = (V, E)con un vértice de origen s ϵ Vy un vértice de sumidero t ϵ V, y donde cada borde (u, v) ϵ Edel gráfico (nodos de conexión u ϵ Vy v ϵ V) tiene 2 cantidades asociadas:

1. c(u, v) >= 0, la capacidad del borde
2. a(u, v) >= 0, el costo de enviar una unidad a través del borde

Definimos una función 0 <= f(u, v) <= c(u, v)como el número de unidades que se pasan a través de un borde dado (u, v). Por lo tanto, el costo de un borde dado (u, v)es a(u, v) * f(u, v). El problema de flujo de costo mínimo se define como minimizar el costo total en todos los bordes para una cantidad de flujo ddada, dada por la siguiente cantidad:

Las siguientes restricciones se aplican al problema:

1. Requisitos de capacidad : el flujo a través de un borde dado no puede exceder la capacidad de ese borde ( f(u, v) <= c(u, v)).
2. Simetría de inclinación : el flujo a través de un borde dado debe ser antisimétrico cuando se invierte la dirección ( f(u, v) = -f(v, u)).
3. Conservación del flujo : el flujo neto en cualquier nodo no fuente sin sumidero debe ser 0 (para cada uno u ∉ {s, t}, sumando todo w, sum f(u, w) = 0).
4. Flujo requerido : el flujo neto fuera de la fuente y el flujo neto hacia el sumidero deben ser iguales al flujo requerido a través de la red (sumando todo u, sum f(s, u) = sum f(u, t) = d).

Dada una red de flujo Gy un flujo requerido d, genere el costo mínimo para enviar dunidades a través de la red. Puede suponer que existe una solución. dy todas las capacidades y costos serán enteros no negativos. Para una red con Nvértices etiquetados con [0, N-1], el vértice de origen será 0y el vértice de sumidero será N-1.

Este es el código de golf , por lo que gana la respuesta más corta (en bytes). Recuerde que esta es una competencia dentro de los idiomas, así como entre los idiomas, así que no tenga miedo de publicar una solución en un idioma detallado.

Los elementos integrados están permitidos, pero le recomendamos que incluya soluciones sin componentes integrados, ya sea como una solución adicional en la misma respuesta o como una respuesta independiente.

La entrada puede ser de cualquier manera razonable que incluya las capacidades y los costos de cada borde y la demanda.

Casos de prueba

Los casos de prueba se proporcionan en el siguiente formato:

c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>

c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213

Estos casos de prueba se calcularon con la biblioteca NetworkX Python .

[R + lpsolve ], 201 186 149 144 bytes

function(c,a,d,`^`=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))$objv

Pruébalo en línea!

El código construye el siguiente problema lineal y lo resuelve usando el lpSolvepaquete:

$$\begin{align} min & \sum_{\forall x \in V}\ \sum_{\forall y \in V} A_{x,y} \cdot f_{x,y} \\ subject\ to : & \\ & \sum_{x \in V} f_{v,x} - f_{x,v} = 0 & \forall v \in V : v \neq \{s,t\} \\ & \sum_{x \in V} f_{s,x} - f_{x,s} = d \\ & \sum_{x \in V} f_{t,x} - f_{x,t} = -d \\ & f_{x,b} \leq C_{x,b} & \forall x \in V,\forall y \in V \end{align}$$

• $V$
• $s$
• $t$
• $A_{x,y}$x -> y
• $f_{x,y}$x -> y
• $d$$t$$s$
• $C_{x,y}$x -> y

Wolfram Language, 42 bytes

FindMinimumCostFlow[#,1,VertexCount@#,#2]&

Trivial incorporado. Solución no incorporada próximamente.

Python 3 + NetworkX , 137 bytes

from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)

Sin enlace TryItOnline porque TIO no tiene instalada la biblioteca NetworkX

Toma la entrada del gráfico como una lista de borde con atributos de capacidad y peso, como este:

[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]

Esta es una versión de golf del código que utilicé para verificar los casos de prueba.