È necessario ridurre al minimo il funzionale

Question

Considera la città come una griglia $ n $ x $ n $. Pertanto, ci sono $ (n+1) (n+1) $ di giunzioni e $ 2n (n+1) $ a due vie. Ogni incrocio ha un'altezza. È noto che l'intersezione in alto a sinistra ha un'altezza di $ 0 $ e più in basso a destra è l'altezza di $ 1 $. Per ogni strada sappiamo quante persone vanno in ogni direzione su questa strada. In questo caso, se la strada conduce dall'intersezione $ i $ all'incrocio $ j $ e la differenza di altezza $ h = h_j - h_i $, l'inconveniente di spostare ogni persona su questa strada è uguale a $ max (h, 0) $. Per tutte le intersezioni tranne due angoli possono scegliere qualsiasi altezza. È necessario ridurre al minimo l'inconveniente totale. Alla fine, è necessario ottenere solo un inconveniente totale, le altezze individuali non sono necessarie.

Penso che tutte le altezze si troveranno nel set $ {0, 1 } $. È chiaro che puoi onestamente scorrere tutte le bitmap e scegliere il meglio. Ma devi trovare un algoritmo più efficiente. Una delle mie idee era quella di mettere tutti gli incroci nella parte in alto a sinistra dell'altezza equivale a $ 0 $ e la parte inferiore destra dell'altezza pari a $ 1 $. Qui sarebbe necessario trovare il limite ottimale. Ho trovato un modo di risolvere trovando il massimo flusso del costo minimo in $ O (n^8) $. Può essere meglio?

Esempio:

PS Scusa per il mio cattivo inglese.