== include(page="template/taskheader" task_id="metrou2") ==

$Această problemă este dedicată celor care aşteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.$

_Această problemă este dedicată celor care aşteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei._

Se dă planul unei reţele de metrou cu $N$ staţii şi $M$ tuneluri bidirecţionale între staţii. Două staţii de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare staţie $i$ are asociat un profit $p{~i~}$ dat.
Henry a fost recent promovat dintr-un post de angajat al departamentului de curăţenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii reţele de metrou, Henry trebuie să aleagă o submulţime de staţii care vor fi construite, astfel încât oricare două staţii alese să nu fie vecine în planul iniţial. Pentru a-şi păstra poziţia în companie, suma profiturilor staţiilor alese în această submulţime trebuie să fie maximă.