I grafi offrono uno strumento di modellazione potente per questo problema. Abbiamo un nodo per ogni grattacielo e coloriamo di nero i nodi con trampolino. Dai nodi neri e' possibile "saltare" ad ogni altro nodo, mentre altrimenti dobbiamo limitarci a seguire gli archi. Abbiamo un arco diretto da i a j se |i-j| = 1 e h[j]<=h[i]. Due proprieta' lavorano al collocare il problema in P: (1) una volta che si sia deciso di raggiungere un nodo v, tanto vale allora visitare tutti i nodi della sua componente fortemente connessa; proof: dopo averli visitati puoi sempre ritornare in v come se nulla fosse stato; (2) una volta che si sia raggiunto un qualsiasi nodo nero v, tanto vale allora visitare tutti i nodi dai quali esista un cammino che conduca ad un nodo nero. proof: puoi visitarli semplicemente saltando a loro, e, dopo averli visitati, puoi sempre ritornare al nodo v portandoti prima a quel nodo nero raggiungibile e poi saltando in v. Possiamo quindi pensare di avere un DAG, in cui alcuni nodi sono neri, ed ad ogni nodo e' associato un valore intero (numero di nodi originali che esso rappresenta). In questo DAG dobbiamo chiederci le seguenti cose: 1. se dal nodo di partenza possiamo raggiungere un nodo nero; 2. quali sono i nodi dai quali e' possibile raggiungere un nodo nero; 3. quali sono i nodi da raggiungere senza mai piu' pervenire ad un trampolino. La (1) trova risposta nella (2), la quale puo' essere risolta con una BFS o DFS a ritroso partendo da un nodo ausiliario collegato a tutti i nodi neri. Dobbiamo poi ricercare nel DAG dei nodi rimanenti (non visitati da BFS o DFS) il piu' lungo cammino pesato che parta dal nodo di partenza se la risposta ad (1) e' negativa, oppure libero (partenza nel nodo che preferisce) se la risposta ad (1) e' positiva. Quindi i grafi ci aiutano nel trovare una soluzione del problema sul piano concettuale.Siamo ora chiamati a semplificare tale soluzione per giungere ad un'implementazione conveniente. Consiglio a tale proposito di leggere ora la soluzione proposta da COCI.