Fişierul intrare/ieşire:metrou2.in, metrou2.outSursăONI 2015 Clasele 11-12
AutorVlad GavrilaAdăugată deassa98Andrei Stanciu assa98
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 pi 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 pi 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 ≤ pi ≤ 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

metrou2.inmetrou2.out
8 10
1 3 2 5 4 1 2 1
1 2
2 3
3 4
4 5
5 3
3 6
2 6
2 7
7 8
8 3
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?