La o firmă de software se lucrează la un mare proiect. Proiectul constă în executarea a n (n număr natural) faze de dezvoltare, numerotate cu numerele 1, 2, …, n. Unele faze pot fi executate în paralel (în acelaşi timp), însă executarea altor faze nu poate fi începută până când nu se finalizează executarea anumitor faze.

Cerinţă

Să se scrie un program care să se determine:

a) timpul minim t în care se poate finaliza executarea proiectului
b) pentru fiecare fază k (k din {1,2,…,n}), momentul de timp c_k la care poate începe faza k cel mai devreme, respectiv momentul de timp d_k la care poate începe faza k cel mai târziu, fără a influenţa durata totală de executare a proiectului.

Date de intrare

Fişierul de intrare pm.in conţine:

pe prima linie, un număr natural n, reprezentând numărul fazelor proiectului
pe a doua linie, n numere naturale, separate prin câte un spaţiu, reprezentând timpul necesar finalizării fiecărei faze
pe fiecare linie k dintre următoarele n linii, un număr natural m_k şi un şir a format din m_k numere naturale: a₁, a₂,…, a_mk, cele m_{+1 numere din linie fiind separate prin câte un spaţiu, m_k reprezentând numărul de faze ce trebuie finalizate înaintea începerii fazei k, iar numerele din şirul a reprezentând numerele de ordine ale fazelor ce trebuie finalizate înaintea începerii fazei k.}

Date de ieşire

Fişierul de ieşire pm.out va conţine n+1 linii. Pe prima linie se va scrie numărul natural t, iar pe fiecare linie k dintre următoarele n linii, se vor scrie cele două numere naturale c_k şi d_k, separate prin câte un spaţiu.

Restricţii şi precizări

0 ≤ n ≤ 100; n – număr natural
Timpul necesar finalizării executării oricărei faze nu va depăşi 1.000.000
Se consideră că executarea proiectului începe la momentul de timp 0
Nu vor exista dependenţe circulare (proiectul întotdeauna se poate finaliza)

Exemplu

pm.in

7
2 3 5 3 3 3 2
0
0
1 2
1 1
1 1
3 3 4 5
1 3

pm.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Project Management:

#include <fstream>
#include <iostream>
using namespace std;
#define MAX 105
int n, a[MAX][MAX],v[MAX], final[MAX],timee;
long timp[MAX], devreme[MAX], tarziu[MAX];
 
void dfs(int x){
    v[x]=1;
    for(int i=1;i<=n;i++)
        if(v[i] == 0 && a[x][i]==1)
            dfs(i);
    timee++;
    final[n-timee+1] = x;
}
 
void read(){
    ifstream fin("pm.in");
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>timp[i];
    for(int i=1;i<=n;i++){
        int m,j;
        fin>>m;
        for( ; m ; --m){
            fin>>j;
            a[j][i] = 1;
            devreme[i]++; //gradul interior
            tarziu[j]++; //gradul exterior
        }
    }
}
 
int main(){
    read();
    for(int i=1;i<=n;i++)
        if(devreme[i]==0)
            a[0][i]=1;
    for(int i=1;i<=n;i++)
        if(tarziu[i]==0)
            a[i][n+1]=1;
    for(int i=1;i<=n;i++)
        devreme[i]=tarziu[i]=0;
     
    for(int i=1;i<=n;i++)
        if(!v[i])
            dfs(i);
    final[n+1] = n+1;
    for(int i=1;i<=n+1;i++)
    {
        int k=final[i];
        for(int j=0;j<i;++j)
            if(a[final[j]][k]==1 && devreme[k]<devreme[final[j]]+timp[final[j]])
                devreme[k]=devreme[final[j]]+timp[final[j]];
    }
    tarziu[n+1] = devreme[n+1];
    for(int i=n;i; --i){
        int k = final[i];
        tarziu[k] = 1<<30;
        for(int j=i+1;j<=n+1;++j)
            if(a[k][final[j]]==1 && tarziu[k] > tarziu[final[j]] -timp[k])
                tarziu[k] = tarziu[final[j]] -timp[k];
    }
    ofstream fout("pm.out");
    fout<<devreme[n+1]<<endl;
    for(int i=1;i<=n;i++)
        fout<<devreme[i]<<" "<<tarziu[i]<<endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1101 Project Management

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1101 Project Management de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1101 Project Management