Fişierul intrare/ieşire:	metrou2.in, metrou2.out	Sursă	ONI 2015 Clasele 11-12
Autor	Vlad Gavrila	Adăugată de	Andrei Stanciu •assa98
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Metrou2

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ă.

Cerinta

Dându-se N, M, profiturile aduse de fiecare din cele N staţii şi planul iniţial al reţelei, să se determine suma maximă a profiturilor staţiilor pe care le poate alege Henry astfel încât oricare două staţii alese să nu fie vecine în planul iniţial.

Date de intrare

Pe prima linie a fişierului de intrare metrou.in se vor afla două numere naturale N şi M separate printr-un spaţiu, reprezentând numărul de staţii, respectiv numărul de tuneluri din planul iniţial. Pe a doua linie se vor afla N numere naturale separate prin câte un spaţiu, al i-lea dintre acestea reprezentând profitul p_i adus dacă staţia i ar fi construită. Pe următoarele M linii se vor afla câte două numere naturale x şi y separate printr-un spaţiu, semnificând faptul că un tunel uneşte staţiile x şi y în planul iniţial.

Date de ieşire

În fişierul de ieşire metrou.out se va afişa o singură linie conţinând un singur număr natural, reprezentând suma maximă a profiturilor staţiilor pe care le poate alege Henry astfel încât oricare două staţii alese să nu fie vecine în planul iniţial.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 150 000
• 1 ≤ x, y ≤ N
• 1 ≤ p_i ≤ 10 000, pentru orice i, 1 ≤ i ≤ N.
• Există maximum 15 staţii care se învecinează cu 3 sau mai multe staţii în planul dat.
• Există maximum 20 de staţii care se învecinează cu exact o staţie în planul dat.
• Pentru 20% din teste, N ≤ 20.
• Pentru alte 10% din teste, planul reţelei de metrou este de forma unui lanţ simplu într-un graf neorientat.
• Pentru alte 10% din teste, planul reţelei de metrou este de forma unui ciclu simplu într-un graf neorientat.
• Putem ajunge din orice staţie în oricare altă staţie urmând tunelurile existente în planul iniţial.

Exemplu

Cum se trimit solutii?