Reabilitarea drumurilor

Într-o ţară oarecare, drumurile naţionale sunt într-o avansată stare de degradare. Ministerul drumurilor elaborează un program de reabilitare a drumurilor naţionale. 
În acest scop a elaborat o hartă pe care sunt marcate oraşele ţării şi drumurile naţionale de legătură dintre acestea. Pentru fiecare segment de drum naţional dintre două oraşe, ministerul a estimat costul reabilitării segmentului respectiv. Deoarece fondurile sunt dificil de obţinut, Ministerul va reabilita numai unele drumuri naţionale, respectând următoarele condiţii: 
1.  costul total al segmentelor de drum reabilitate să fie minim; 
2.  între oricare două oraşe ale ţării să se poată circula numai pe segmente de drum reabilitate. 
Să se determine segmentele de drum care trebuie să fie reabilitate.