Fişierul intrare/ieşire:soc2.in, soc2.outSursălot 2006
AutorMugurel Ionut AndreicaAdăugată deazotlichidAdrian Vladu azotlichid
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Soc 2

Un grup de N oameni de afaceri s-au antalnit cu ocazia unei conferinte. Unii dintre ei sunt dusmani, altii nu (de prietenie nu se prea pune problema cand este vorba de afaceri). Fiecare dintre ei are un cont in banca 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 nu fie dusmani, 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 dusmanie dintre ei. Analizand problema, ati ajuns la concluzia ca relatiile de dusmanie 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 dusmani (dusmania este reciproca). Graful are o structura speciala, mai exact el este un graf cordal. Un graf se numeste graf cordal daca indeplineste una dintre urmatoarele 2 conditii:

  1. Este un graf cu un singur nod.
  2. Se obtine inserand un nod nou X intr-un graf cordal G, astfel: se alege o submultime de noduri din G, cu proprietatea ca exista muchie intre oricare doua noduri din submultime (submultimea poate contine si doar un singur nod), si se introduce cate o muchie intre nodul nou inserat X si fiecare nod din submultime.

O definitie echivalenta a grafurilor cordale este urmatoarea: un graf se numeste graf cordal daca este conex si orice ciclu elementar (ce contine fiecare nod al grafului cel mult o data) avand cel putin 4 noduri contine cel putin o "coarda" (o muchie intre doua noduri care fac parte din ciclu, dar nu sunt adiacente pe ciclu).
In continuare, iata cateva exemple de grafuri cordale si grafuri care nu sunt cordale :

Date de intrare

Pe prima linie a fisierului de intrare 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 dusmani.

Date de iesire

In fisierul de iesire 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. Numerele oamenilor de afaceri pot fi afisate in orice ordine (nu neaparat in ordine crescatoare).

Restrictii

  • 2 ≤ N ≤ 256
  • 1 ≤ M ≤ N * (N - 1) / 2
  • 1 ≤ Ei ≤ 1 000 000, pentru i = 1, 2, ..., N
  • Daca determinati doar capitalul maxim al societatii, dar nu si actionarii acesteia, veti primi 60% din punctajul corespunzator testului respectiv.
  • In cazul a 20% din fisierele de test, M = N - 1
  • In cazul a 60% din fisierele de test, fiecare componenta biconexa a grafului dat va contine maxim 15 noduri

Exemplu

soc2.insoc2.out
16 31
4 4 4 3 1 5 5 3 2 3 1 1 3 5 4 4
1 3
1 8
1 9
1 10
2 4
2 7
2 13
3 4
3 7
3 8
3 9
3 10
3 13
3 16
4 7
4 13
5 6
5 7
5 15
6 7
6 15
7 11
7 13
7 15
8 9
9 10
10 12
10 14
10 16
11 15
12 14
23
6
1 2 6 11 14 16
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content