Fabrica

#include<fstream>
#include<iostream>
using namespace std;
ifstream f("datein.in");

int c[101],maxim=0,n,neah=-1,a[102][102];

void citire()
{
    int i,j,k,cost;
    f>>n;
    for(i=1; i<=n+1; i++)
        for(j=1; j<=n+1; j++)
            if(i==j) a[i][j]=0;
            else  a[i][j]=neah;
    for(i=1; i<=n; i++)
        f>>c[i];
    for(i=1; i<=n; i++)
    {
        f>>k;
        for(j=1; j<=k; j++)
        {
            f>>cost;
            a[cost][i]=c[cost];
        }
    }
    a[n][n+1]=c[n];
}

void afis()
{
    int i,j;
    cout<<endl;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            if(a[i][j]<0) cout<<"# ";
            else cout<<a[i][j]<<" ";
        cout<<endl;
    }
}

void rf()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(a[i][j]<a[i][k]+a[k][j] && a[i][k]!=-1 && a[k][j]!=-1)
                {
                    a[i][j]=a[i][k]+a[k][j];
                    if(a[i][j]>maxim) maxim=a[i][j];
                }
}

int main()
{
    citire();
    cout<<"Matricea costurilor (duratelor):";
    afis();
    rf();
    cout<<"\n\nMatricea costurilor (duratelor) maxime:";
    afis();
    cout<<endl<<maxim+c[n]<<"(durata productiei)"<<endl;
    for(int i=1; i<=n; i++)
    {
        long mmm=0;
        for(int j=1; j<=n; j++)
            if(a[j][i]>mmm)  mmm=a[j][i];
        cout<<"Cel mai devreme pentru sectia "<<i<<": "<<mmm<<", iar cel mai tarziu ";
        if(maxim>a[i][n]) cout<<maxim-a[i][n]<<endl;
        else cout<<0<<endl;
    }
}
///     Intr-o fabrica exista n sectii numerotate de la 1 la n in 3 categorii:
///-sectii de intrare, adica sectii prin care intra in fabrica materii prime
///-sectii intermediare, care primesc produse intermediare de la alte sectii, le prelucreaza si le transmit la randul lor altor sectii
///-sectia numerotata cu n care este o sectie de finalizare a productiei
///     Pentru fiecare sectie dintre cele n se cunosc urmatoarele informatii:
///-durata necesara pentru prelucrarea in sectia respectiva
///-numarul sectiilor si sectiile care furnizeaza produse intermediare sectiei curente
///     Stiind ca durata transportului produselor intermediare intre sectii este neglijabila, ca in fabrica nu se formeaza circuite de productie si ca o sectie poate sa-si inceapa activitatea doar dupa sect care furnizeaza materii le-au furnizat.
///     Calculati urmatoarele:
///- timpul necesar pt fabricarea produsului finit
///- pt fiecare sectie timpul cel mai devreme ca sa poata incepe productia si timpul cel mai tarziu in care poate incepe productia astfel incat durata totala a productiei sa nu fie afectata.
///     Observatii:
///- sectiile fabriici pot lucra simultan
///- sectiile de intrare pornesc cel mai devremea la momentul 0.
///     Indicatii:
///- duratele din varfuri se se muta pe arce
///- se construieste matrice a costurilor (duratelor)
///- se aplica algoritmul Roy-Floyd pentru drum de cost maxim
///- durata productiei este maximul de pe ultima linia adunat cu durata de prelucrare din sectia n
///- cel mai repede o sectie poate incepe productia dupa ce au ajuns in ea produsele din sectiile de care depinde, adica maximul de pe coloana
///- cel mai tarziu o sectie poate incepe productia astfel incat durata productiie de la ea la ultima sectie sa nu fie mai mare decat durata de productie a celorlalte sectii, si se obtine prin diferenta de pe ultima coloana dintre maxim si fiecare element (durata corespunzatoare fiecarei sectii).
/*date.in
12 (n)
3 1 8 3 5 3 6 7 1 7 9 6 (costurile)
0 (sectia 1 nu depinde de alta)
2 1 10 (sectia 2 depinde de 2 sectii, si anume de 1 si 10)
3 2 4 9
2 10 11
1 3
2 3 7
2 4 9
2 3 7
1 11
0
0
3 5 6 8
date.out
matricea initiala:
0 3 # # # # # # # # # #
# 0 1 # # # # # # # # #
# # 0 # 8 8 # 8 # # # #
# # 3 0 # # 3 # # # # #
# # # # 0 # # # # # # 5
# # # # # 0 # # # # # 3
# # # # # 6 0 6 # # # #
# # # # # # # 0 # # # 7
# # 1 # # # 1 # 0 # # #
# 7 # 7 # # # # # 0 # #
# # # 9 # # # # 9 # 0 #
# # # # # # # # # # # 0

matricea costurilor maxime
0 3 4 # 12 12 # 12 # # # 19
# 0 1 # 9 9 # 9 # # # 16
# # 0 # 8 8 # 8 # # # 15
# # 3 0 11 11 3 11 # # # 18
# # # # 0 # # # # # # 5
# # # # # 0 # # # # # 3
# # # # # 6 0 6 # # # 13
# # # # # # # 0 # # # 7
# # 1 # 9 9 1 9 0 # # 16
# 7 10 7 18 18 10 18 # 0 # 25
# # 12 9 20 20 12 20 9 # 0 27
# # # # # # # # # # # 0
33 (durata productiei)
0 8 (cel mai devreme, cel mai tarziu)
7 11
12 12
9 9
20 22
20 24
12 14
20 20
9 11
0 2
0 0
27 27
*/