turism2

Turism2

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

Andreea si Ioana au ajuns in judetul Tinichea si doresc sa viziteze cat mai multe obiective turistice. Judetul Tinichea este format din $N$ orase, intre unele dintre aceste orase existand sosele bidirectionale. Mai exact, orice sosea leaga direct doua orase, iar soselele sunt dispuse astfel incat intre oricare doua orase din judet sa existe un drum unic. Un drum este o succesiune de orase astfel incat intre oricare doua orase consecutive pe drum exista o sosea ce le leaga. Orasele sunt numerotate de la $1$ la $N$ si pentru fiecare oras se cunoaste $C{~i~}$, numarul de obiective turistice din orasul $i$.
Fiindca s-au certat putin in ultima vreme, cele doua fete vor sa aleaga fiecare cate un drum astfel incat numarul de obiective pe care le viziteaza Andreea adunat cu numarul de obiective pe care le viziteaza Ioana sa fie maxim. Conditiile pe care le pun fetele sunt ca drumurile lor sa nu aibe niciun oras in comun, iar orice oras sa fie vizitat cel mult o singura data.

Andreea si Ioana au ajuns in judetul Tinichea si doresc sa viziteze cat mai multe obiective turistice. Judetul Tinichea este format din $N$ orase, intre unele dintre aceste orase existand sosele bidirectionale. Mai exact, orice sosea leaga direct doua orase, iar soselele sunt dispuse astfel incat intre oricare doua orase din judet sa existe un drum unic. Un drum este o succesiune de orase astfel incat intre oricare doua orase consecutive pe drum exista o sosea ce le leaga. Orasele sunt numerotate de la $1$ la $N$ si pentru fiecare oras se cunoaste $C{~i~}$, numarul de obiective turistice din orasul $i$. Fiindca s-au certat putin in ultima vreme, cele doua fete vor sa aleaga fiecare cate un drum astfel incat numarul de obiective pe care le viziteaza Andreea adunat cu numarul de obiective pe care le viziteaza Ioana sa fie maxim. Conditiile pe care le pun fetele sunt ca drumurile lor sa nu aibe niciun oras in comun, iar orice oras sa fie vizitat cel mult o singura data.

h2. Cerinta

h3. Explicatie

Fişierul de intrare trebuie sa contina $12$ teste, in exemplu sunt prezentate doar primul si ultimul dintre cele $12$. Pentru primul test exista $2$ orase, in fiecare oras fiind cate un obiectiv turistic. Exista o singura sosea (de la $1$ la $2$). Soluţia optima este $2$ (fiecare fata viziteaza cate un oras).

Fisierul de intrare trebuie sa contina $12$ teste, in exemplu sunt prezentate doar primul si ultimul dintre cele $12$. Pentru primul test exista $2$ orase, in fiecare oras fiind cate un obiectiv turistic. Exista o singura sosea (de la $1$ la $2$). Solutia optima este $2$ (fiecare fata viziteaza cate un oras).

Pentru ultimul test exista $3$ orase, avand $1$, $2$ respectiv $3$ obiective turistice) si $2$ sosele (intre $1$ si $2$, respectiv intre $1$ si $3$). Solutia optima este $6$. Punctele de suspensie (...) indica faptul ca lipsesc cele $10$ teste.
== include(page="template/taskfooter" task_id="turism2") ==