Probleme de informatica - enunturi si rezolvari

Intr-o fabrica exista n sectii numerotate de la 1 la n si impartite 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.
Oservatii:
- 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).
Exemplu:
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 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

#include<fstream>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");

int c[101],mm=0;
int n;
int minn=-1000000;
int a[102][102];

void citire(int a[102][102],int &n)
{ int i,j,k,x;
  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]=minn;
  for(i=1;i<=n;i++)
      f>>c[i];
  for(i=1;i<=n;i++)
  { f>>k;
    for(j=1;j<=k;j++)
      { f>>x;
        a[x][i]=c[x];
      }
  }
  a[n][n+1]=c[n];
}

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

void rf(int a[102][102],int n)
{ 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]!=minn && a[k][j]!=minn)
	{ a[i][j]=a[i][k]+a[k][j];
	  if(a[i][j]>mm) mm=a[i][j];
        }
}

int main()
{
  citire(a,n);
  afis(a,n);
  rf(a,n);
  afis(a,n);
  g<<mm+c[n]<<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];
    g<<mmm<<" ";
    if(mm>a[i][n]) g<<mm-a[i][n]<<endl;
    else g<<0<<endl;
  }
  f.close();
  f.close();
  return 0;
}

21 nov 2024

Site-ul conține 884 de probleme rezolvate