Lista de probleme 2

Pentru a testa o nouă topologie s-a construit o reţea de calculatoare în care fiecare calculator transmite informaţia unidirecţional către un singur calculator din reţea. Numim conexiune o pereche ordonată de calculatoare, nu neapărat distincte, în care primul este cel care trimite informaţia iar al doilea este cel care o recepţioneaza direct. Fiind dată o astfel de reţea şi conexiunile existente între calculatoarele care o alcătuiesc, să se determine submulţimea cu număr maxim de calculatoare-feed-back. Un calculator-feed-back are proprietatea că informația ce pleacă de la acesta ajunge, prin intermediul conexiunilor succesive, înapoi la calculatorul de la care a plecat.

Scrieţi un program care, pentru o reţea cu n calculatoare numerotate de la 1 la n şi conexiuni precizate, determină submulţimea cu număr maxim de calculatoare-feed-back.

O recunoscută companie internaţională a deschis în oraş două fabrici de ciocolată şi n centre de distribuţie. Fabricile produc un singur sortiment de ciocolată şi utilizează ca ambalaj un singur model de cutii. Fiind o companie eficientă dar preocupată de reducerea poluării în oraş, pentru livrarea săptămânală a comenzilor la centrele de distribuţie se foloseşte doar o maşină. Au fost estimate costurile de transport a unei cutii cu ciocolată de la fiecare dintre cele două fabrici la fiecare centru. În fiecare săptămână, producţia cumulată a celor două fabrici acoperă exact cererile celor n centre.

Scrieţi un program care calculează costul minim de transport săptămânal pentru livrarea comenzilor la cele n centre de distribuţie, cunoscând cantităţile produse de cele două fabrici, cererea fiecărui centru de distribuţie şi costurile de transport ale unei cutii cu ciocolată de la fiecare fabrică la fiecare centru.