#include
#include
#include
using namespace std;

class Wierzcholek
{
public:
int nr;
int t_min;
int t_max;
int luz;
int tn;
int tgr;
int Kn;
int Kgr;
//double S;

Wierzcholek()
{
t_min = 0;
t_max = 0;
nr = -1;
luz = 0;
}

void Wyswietl()
{
cout<<"Numer : "< cout<<"T Min : "< cout<<"T Max : "< cout<<"Luz : "< }

void ObliczLuz()
{
luz = t_max - t_min;
}



};



class CPM
{
public:
int ile_w;//ilość wierzchołków
int ile_k;//ilość krawędzi
int tab[100][100];//['wiersze']['kolumny']


Wierzcholek w[100];
void init()
{
//Czyszczenie
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
tab[i][j]=-1;
//Interface
cout << "Podaj ilość wierzchołków:\n";
cin >> ile_w;
cout << "Podaj ilość krawędzi:\n";
cin >> ile_k;

double*gradient=new double[ile_k];
int tmp_p,tmp_k,tmp_t,tgr,Kn,Kgr;
//double gradient;

for(int i=0;i {
cout< cout<<"Podaj i: "; cin>>tmp_p;
cout<<"Podaj j: "; cin>>tmp_k;
cout<<"Podaj czas pracy: "; cin>>tmp_t;
cout<<"Podaj czas graniczny tgr: ";
cin>>tgr;
cout<<"Podaj Kn: "; cin>>Kn;
cout<<"Podaj Kgr: "; cin>>Kgr;


if((tmp_t-tgr)!=0)
{
gradient[i]=(Kgr-Kn)/(tmp_t-tgr);
}
else
{
gradient[i]=0;
}

cout<<"S="<
tab[tmp_p-1][tmp_k-1]=tmp_t;
tmp_p=tmp_k=tmp_t=0;

}

///wyszukiwanie najmniejszego gradientu
double min=gradient[0];
for(int i=0; i {
if((gradient[i]>0)&(min {
min=gradient[i];


}
}
Numeruj();
//Wyswietl();
Sortuj();
MinTerminy();
MaxTerminy();
//ObliczS();
Luzy();
///SrGradient();
Wyswietl();
WyznaczSciezke();
Tn();
}




void Numeruj() //Numerowanie wierzchołków grafu
{
bool ss=false;
int tmp_tab[100][100];

//Czyszczenie
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
tmp_tab[i][j]=-1;

//Kopiowanie
for(int i=0;i for(int j=0;j tmp_tab[i][j]=tab[i][j];

//Wyznaczam Pierwszy
for(int k=0;k {
for(int i=0;i {
ss=false;
for(int j=0;j if(tmp_tab[j][i] != -1 || tmp_tab[j][i] == -2)
ss=true;
if(ss == false)
{
w[i].nr=k;
for(int j=0;j {
if(tmp_tab[i][j] != -2)
tmp_tab[i][j] = -1;
}
for(int j=0;j {
tmp_tab[j][i] = -2;
}
//cout << k << "-" << i << endl;
break;
}
}
}
}

void Sortuj() //Numerowanie wierzchołków grafu
{
int tmp_tab[100][100],id,tmp,changes[100];

//Czyszczenie
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
{
tmp_tab[i][j]=-1;
changes[i]=NULL;
}

//Kopiowanie
for(int i=0;i for(int j=0;j tmp_tab[i][j]=tab[i][j];

//Czyszczenie
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
tab[i][j]=-1;
//Sortuje
for(int k=0;k {
if(k == 0)
id=0;
else
{
for(int i=0;i if(w[i].nr == k)
{
id = i;
break;
}
}

//Zamiana miejsccami kolumn i wierszy
for(int j=0;j tab[k][j]=tmp_tab[id][j];
if(k != id)
{
bool ch = false;
for(int l=0;l if(changes[l] == k || changes[l] == id)
ch = true;
//cout << k << '-' << id < w[id].nr = id;
if(!ch)
{
for(int j=0;j {
tmp = tab[j][k];
tab[j][k] = tab[j][id];
tab[j][id] = tmp;
}
changes[k]=k;
}
}
}
}


void MinTerminy()
{
int min[100],ile=0;

//Czyszczenie
for(int i=0;i<100;i++)
min[i]=NULL;

//Wyznaczam Pierwszy
for(int k=1;k {
for(int i=0;i if(tab[i][k] >= 0)
{
min[ile] = tab[i][k]+w[i].t_min;
ile++;
}
if(ile < 2)
{
w[k].t_min = min[0];
min[0] = 0;
} else {
for(int i=1;i if(min[0] < min[i])
min[0] = min[i];
w[k].t_min = min[0];
//Czyszczenie
for(int i=0;i<100;i++)
min[i]=NULL;
}
ile=0;
//cout << k << "-" << w[k].nr << " -> " << w[k].t_min < }
}

void MaxTerminy()
{
int max[100],ile=0;

//Czyszczenie
for(int i=0;i<100;i++)
max[i]=NULL;
//Wyznaczam Pierwszy
w[ile_w-1].t_max = w[ile_w-1].t_min;
for(int k=ile_w-2;k>=0;k--)
{
for(int i=0;i if(tab[k][i] >= 0)
{
max[ile] = w[i].t_max-tab[k][i];
ile++;
}
if(ile < 2)
{
w[k].t_max = max[0];
max[0] = 0;
} else {
for(int i=1;i if(max[0] > max[i])
max[0] = max[i];
w[k].t_max = max[0];
//Czyszczenie
for(int i=0;i<100;i++)
max[i]=NULL;
}
ile=0;
//cout << k << "->" << w[k].t_max < }
}

void Luzy()
{
for(int i=0;i w[i].ObliczLuz();
}

void Tn()
{
for(int i=0;i w[i].ObliczTn();

}


void WyznaczSciezke()
{
int wynik=0;
int czas_kryt=0;
int czas_nkryt=0;
cout< cout<<"Sciezka krytyczna: "<
for(int k=0;k for(int i=0;i {
if(tab[k][i] >= 0)
{
wynik = w[i].t_max - w[k].t_min - tab[k][i];
//cout << wynik << " " << endl;
if(wynik == 0 && w[i].luz == 0)
{
cout << (k+1) << " -> "; czas_kryt+=w[k].tn;
if((k+2) == ile_w)
cout << (k+2);


}
}
wynik=0;
}

//cout< }
void Wyswietl()
{

for(int i=0;i {
for(int j=0;j {
if(tab[i][j] >= 0)
cout << setw(3) << tab[i][j];
else
cout << setw(3) << "-";
}
cout << endl;
}
for(int i=0;i {
w[i].Wyswietl();
cout << endl;
}
}
};

int main()
{
locale myloc ("Polish");
locale oldloc = locale::global (myloc);
CPM *engine = new CPM();
engine->init();//Wpiszujesz z palca
locale::global (oldloc);
cin.ignore();
cin.get();
return 0;
}