Fişierul intrare/ieşire:soc.in, soc.outSursăLot 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Soc

Un grup de N oameni de afaceri s-au intalnit cu ocazia unei conferinte. Unii dintre ei sunt prieteni, altii nu. Fiecare dintre ei are un cont bancar ce contine o anumita suma exprimata in euro. De fiecare data cand se intalnesc, se gandesc cum sa initieze o noua afacere. De data aceasta s-au decis sa infiinteze o societate, la care actionarii sa fie o parte dintre ei, astfel incat oricare doi oameni de afaceri care sunt actionari ai societatii sa fie prieteni, iar capitalul societatii (egal cu totalul sumelor din conturile actionarilor) sa fie maxim. Pentru a determina actionarii acestei societati, v-au angajat pe dumneavoastra si, daca le veti da raspunsul in timp util, veti fi recompensat cu o suma frumoasa.

Inainte de a va apuca de treaba, cei N oameni de afaceri v-au pus la dispozitie informatii referitoare la conturile lor din banca si la relatiile de prietenie dintre ei. Analizand problema, ati ajuns la concluzia ca relatiile de prietenie pot fi reprezentate sub forma unui graf neorientat cu N varfuri (corespunzatoare celor N oameni de afaceri); intre doua varfuri diferite exista o muchie, daca cei doi oameni de afaceri corespunzatori celor doua varfuri din graf sunt prieteni (prietenia este reciproca). Graful are o structura speciala, mai exact el este un cograf. Un graf se numeste cograf daca indeplineste cel putin una dintre urmatoarele 3 conditii:

  1. Este un graf cu un singur nod
  2. Este graful-reuniune a doua sau mai multe cografuri
  3. Este graful complementar al unui cograf

Prin reuniunea a doua grafuri, unul cu i noduri si muchii intre aceste i noduri, altul cu j noduri si muchii intre aceste j noduri, se obtine un graf cu i+j noduri, care contine toate muchiile din cele doua grafuri, fara a se introduce vreo muchie in plus. De exemplu, pentru doua grafuri, unul avand nodurile etichetate 1 si 2 si continand muchia [1,2], iar altul avand nodurile etichetate 9,10,11 si continand muchiile [9,10], [9,11], graful-reuniune va contine 5 noduri etichetate 1,2,9,10,11 si exact trei muchii: [1,2], [9,10], [9,11].

Graful complementar al unui graf se obtine astfel:

- pentru orice pereche de noduri distincte [a,b] intre care exista muchie in graful initial, NU va exista muchie in graful complementar;
- pentru orice pereche de noduri distincte [a,b] intre care NU exista muchie in graful initial, va exista muchie in graful complementar.

De exemplu, pentru graful avand 3 noduri, etichetate 4,11,20, si 2 muchii [4,11] si [11,20], graful complementar va contine toate cele 3 noduri si o singura muchie: [4,20].

Date de intrare

Pe prima linie a fisierului de intrare soc.in se afla numerele intregi N si M, separate printr-un spatiu. Pe urmatoarea linie se afla numerele intregi Ei, i=1,2,..,N, separate prin cate un spatiu, reprezentand sumele din conturile celor N oameni de afaceri. Numarul EK reprezinta suma din contul afaceristului numerotat cu K. Pe urmatoarele M linii se afla cate doua numere intregi a si b din intervalul [1,N], avand semnificatia ca oamenii de afaceri numerotati cu a si, respectiv, b sunt prieteni.

Date de iesire

In fisierul soc.out veti afisa, pe prima linie, capitalul maxim al societatii. Pe urmatoarea linie veti afisa numarul A, reprezentand numarul de actionari ai societatii. Pe cea de-a treia linie veti afisa numerele oamenilor de afaceri care vor fi actionari, separate prin cate un spatiu. Daca exista mai multe posibilitati de a alege actionarii societatii astfel incat capitalul acesteia sa fie maxim, puteti afisa oricare din ele.

Restrictii si precizari

  • 1 ≤ N ≤ 256
  • 0 ≤ M ≤ N*(N-1)/2
  • 0 ≤ Ei ≤ 1 000 000, pentru i=1,2,..,N
  • Daca sunt mai multe solutii corecte, se va afisa oricare

Exemplu

soc.insoc.out
5 4
5 4 3 3 3
2 1
3 4
4 5
5 3
9
3
3 4 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content