Lista de probleme 227

Filtrare

Se dă un graf orientat aciclic (adică nu există circuite). Lungimea unui drum elementar este dată de numărul de arce. Să se determine lungimea maximă a unui drum elementar în acest graf orientat aciclic.

Undeva, într-un ținut îndepărtat, își desfășoară activitatea o vestită companie, mai exact Mondial Computers SRL. Aceștia lucrează cu mulți clienți de renume, deci au nevoie de multă forță de muncă. Astfel, ei au o bază de date în care mențin informații despre angajații lor, dar, recent, echipa care se ocupa de această bază de date a dat dovadă de un randament scăzut, iar ca urmare a acestui fapt, manager-ul general a decis, fără a ține cont de consecințe, să îi concedieze, iar aceștia, de supărare, au șters înainte de a pleca din companie toate datele angajaților. Acum manager-ul are nevoie de ajutorul vostru(voluntar, desigur) pentru reorganizarea acestei baze de date până reușește să angajeze noi oameni.

Determinați numărul de fețe ale unui graf neorientat, conex, planar.

#4093 Apa

Daniel a descoperit un izvor cu apă cristalină și vrea ca această apă sa ajungă în orașul în care locuiește.

Daniel are și o hartă cu drumuri pe unde se pot crea râuri astfel încât apa de la izvor să ajungă la destinație. Acestea vor avea un debit limitat notat cu c pentru prevenirea inundațiilor.

În apropierea izvorului există și alte orașe pe unde râurile pot să treacă până să ajungă la destinație. Și acestea apar pe hartă, dar pentru că numele lor nu ajută, vor fi notate cu numere de la 2 până la n - 1. Numerele sunt unice și au o semnificație. Cu cât un număr este mai mic, cu atât altitudinea locației notate cu acel număr este mai mare și la fel și invers. De aceea izvorul va fi notat cu 1 pe hartă și destinația cu n, iar Daniel va folosi doar gravitația pentru transportarea apei.

Apa se va deplasa intr-o singură direcție. Un râu care are punctul de plecare i și destinația j, va exista doar dacă i < j. Daniel vrea să ajungă cat mai multă apă în oraș ca toți locuitorii să se bucure de aceasta, dar trebuie să aibă grijă sa nu apară inundații. Ajutați-l pe Daniel să împartă debitul fiecărui râu.

Problemă inspirată de pe Infoarena (Flux maxim)

Se dau un arbore cu N noduri și rădăcina în nodul 1 al cărui muchii au lungimi exprimate prin numere naturale nenule și Q query-uri de forma u v. Pentru fiecare query să se afle suma lungimilor tuturor drumurilor distincte de la un nod aflat în subarborele cu rădăcina în nodul u la un nod aflat în subarborele cu rădăcina în nodul v modulo \( {10}^{9} + 7 \)(lungimea unui drum este egală cu suma lungimilor tuturor muchiilor ce îl alcătuiesc).

Se consideră un graf neorientat conex cu n noduri și n muchii. Să se determine numărul arborilor parțiali ai grafului.

#3588 tobruk

În timpul celui de-Al Doilea Război Mondial, armata aliată desfășoară o operațiune de amploare în regiunea nordică a Libiei pentru a sabota aprovizionarea cu petrol a aparatului militar nazist, operațiune cunoscută sub numele de cod “Furtună la Tobruk”, și a dobândi controlul decisiv asupra zonei strategice a Africii de Nord. Se cere determinarea profitului maximal global al misiunii aliate, analizând în prealabil configurația sistemului defensiv inamic și forța de asalt a trupelor aliaților și respectând o serie de restricții predeterminate.

#585 Orase

Într-o țară oarecare sunt n orașe, numerotate de la 1 la n, între care există șosele unidirecționale. Președintele țării vrea să facă o vizită electorală prin mai multe orașe în felul următor: aterizează cu elicopterul în orașul p, merge până în orașul q folosind rețeaua de șosele existentă, de unde pleacă cu elicopterul. Din punct de vedere politic unele orașe sunt sigure (conduse de aliați politici ai președintelui), altele sunt nesigure (conduse de adversari), iar președintele dorește să parcurgă numai orașe sigure.

Consilierii președintelui i-au propus mai multe perechi de orașe p q care pot fi alese ca punct de plecare și de sosire pentru vizită. Președintele vă cere să verificați pentru fiecare pereche dată dacă există un drum care să treacă numai prin orașe sigure.

Avem în cartier un arbore cu nodurile colorate și cu rădăcina nodul 1. Pentru fiecare nod i al arborelui să se afișeze câte culori distincte sunt în subarborele cu rădăcina în i.

Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor.

Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său.