Il est nécessaire de minimiser le fonctionnement

Question

Considérez la ville comme une grille $ n $ x $ n $. Ainsi, il y a $ (n + 1) (n + 1) $ de jonctions et 2 $ (n + 1) Routes bidirectionnelles $. Chaque intersection a une hauteur. Il est connu que l'intersection supérieure gauche a une hauteur de 0 $, et la basse droite la hauteur de 1 $. Pour chaque route, nous savons combien de personnes vont dans chaque direction sur cette route. Dans ce cas, si la route mène de l'intersection $ i $ à l'intersection $ j $ et la différence de hauteur $ h = h_j - h_i $, l'inconvénient de déplacer chaque personne sur cette route est égal à $ max (h, 0) $. Pour toutes les intersections, sauf deux angles sont autorisés à choisir n'importe quelle hauteur. Il est nécessaire de minimiser les inconvénients totaux. En fin de compte, il est nécessaire d'obtenir uniquement un inconvénient total, les hauteurs individuelles ne sont pas nécessaires.

Je pense que toutes les hauteurs se situeront dans l'ensemble $ {0, 1 } $. Il est clair que vous pouvez honnêtement parcourir tous les bitmaps et choisir le meilleur. Mais vous devez trouver un algorithme plus efficace. L'une de mes idées consistait à mettre toutes les intersections dans la partie supérieure gauche de la hauteur équivaut à 0 $, et la partie inférieure droite de la hauteur égale à 1 $. Ici serait nécessaire pour trouver la frontière optimale. J'ai trouvé un moyen de résoudre en trouvant un flux maximal de coût minimum dans $ o (n ^ 8) $. Cela peut-il être mieux?

Exemple:

PS désolé pour mon mauvais anglais.