Répartition des ressources des fournisseurs au nombre maximal de récepteurs

Question

Considérez qu'il y a une ville avec N $ N $ les résidents qui ont besoin d'Internet et il y a $ m $ Fournisseurs Internet dans la ville.Ici, dans la ville, chaque résident a besoin d'Internet et chaque résident sait quels fournisseurs sont à la disposition de lui.Formellement laissez le résident $ i $ a une liste de fournisseurs $ a_i $ .De plus, chaque fournisseur a un nombre maximum de connexions qu'il peut donner, c'est-à-dire, c'est-à-dire que, fournisseur $ i $ peut avoir à max $ k_i$ connexions.Trouvez la manière optimale de fournir à Internet de manière à ce que le nombre d'habitants d'Internet soit maximum.

Mes pensées sur la question est que cette question ressemble à une dérivée de problèmes de knack-pack avec des contraintes, qui suggère une programmation dynamique, mais je suis incapable de trouver les États.Quelqu'un pourrait-il m'aider?

Answer 1

Ce problème est un cas de Problème de flux maximum .

Supposons que nous recevions des fournisseurs Internet $ p_1, p_2, \ CDOTS, p_m $ et résidents $ r_1, r_2, \ CDOT, R_N $ . Envisager un réseau de flux spécifié comme suit.

• Les nœuds sont s, \ p_1, p_2, \ CDOT, p_m, \ r_1, r_2, \ CDOT, r_n, \ t $ , où $ s $ et $ t $ sont deux nœuds supplémentaires debout pour la source et l'évier.
• il y a un bord entre $ s $ et chaque $ p_i $ avec capacité $ k_i $ .
• Il y a un bord entre $ p_i $ et $ r_j $ avec la capacité 1 si $ p_i $ peut fournir Internet à $ r_j $ .
.
• Il y a un bord entre chaque $ r_j $ et $ t $ avec capacité 1.

Ce que nous voulons, c'est trouver le flux maximum de $ s $ à $ t $ . < / p>

Il y a Beaucoup d'algorithmes pour résoudre un problème de débit maximal en temps polynomial. Par exemple, algorithme Ford-Fulkerson et L'algorithme de DINIC est assez populaire. Le code source qui implémente ces algorithmes en différentes langues de programmation peut être facilement trouvé.

Tous ces algorithmes produiront un flux maximal intégré, nous ne nous inquiéterons donc pas si le flux maximal calculé stipule que certains fournisseurs devraient fournir 0,42 ou $ \ frac {\ \ sqrt2} 2 $ Internet à certains résident. Vous pouvez vérifier Le théorème de flux intégral .