Distribución de recursos de proveedores al número máximo de receptores.

Question

Considere que hay una ciudad con $ n $ residentes que necesitan Internet y hay $ m $ Proveedores de Internet en la ciudad.Aquí, en la ciudad, cada residente necesita Internet y cada residente sabe qué proveedores están disponibles para él.Formalmente deja que el residente $ i $ tiene lista de proveedores $ A_I $ .Además, cada proveedor tiene un número máximo de conexiones que puede dar, es decir, proveedor $ i $ puede tener en max $ k_i$ conexiones.Encuentre la forma óptima de proporcionar Internet para que el número de residentes que tengan Internet sea máximo.

Mis pensamientos sobre la pregunta es que esta pregunta se parece a un derivado del problema de los paquetes de Knack con restricciones, lo que sugiere programación dinámica, pero no puedo encontrar los estados.¿Alguien podría ayudarme?

Answer 1

Este problema es un caso de problema de flujo máximo .

Supongamos que se nos dan a los proveedores de Internet $ p_1, p_2, \ cdots, p_m $ y residentes $ r_1, r_2, \ CDOTS, R_N $ . Considere una red de flujo especificada como la siguiente.

• los nodos son $ s, \ p_1, p_2, \ codots, p_m, \ r_1, r_2, \ cdots, r_n, \ t $ , donde $ s $ y $ t $ son dos nodos adicionales de pie para la fuente y el fregadero.
• Hay un borde entre $ s $ y cada $ p_i $ con capacidad $ k_i $ .
• Hay una ventaja entre $ p_i $ y $ r_j $ con capacidad 1 si $ P_I $ puede proporcionar Internet a $ r_j $ .
• Hay un borde entre cada $ r_j $ y $ t $ con capacidad 1.

Lo que queremos es encontrar el flujo máximo de $ s $ a $ t $ . < / p>

Hay Muchos algoritmos para resolver un problema de flujo máximo en el tiempo polinomio. Por ejemplo, algoritmo FORD-FULKERSON y el algoritmo de Dinic es bastante popular. El código fuente que implementa esos algoritmos en varios idiomas de programación se puede encontrar fácilmente.

Todos esos algoritmos producirán un flujo máximo integral, por lo que no nos preocuparemos en caso de que el flujo máximo calculado estipula que algún proveedor debe proporcionar 0,42 o $ \ frac {\ sqrt2} 2 $ internet para algún residente. Puede comprobar el teorema de flujo integral .