Ðåôåðàò: Òðàíñïîðòíàÿ çàäà÷à
break;
}
}
}
}
// ********** Ïðîäîëæåíèå ôóíêöèè ïîäñ÷åòà ïîòåíöèàëîâ *****************
for(;;){
fl = 0;
for(top = topnast;top!=NULL;top =top -> next)
{
if((top -> zn) == -1)
{
if(*(pu+(top ->u)) !=MIN)
{
*(pv+(top->v))=(top->b) - *(pu+(top ->u));
fl = 1;
top -> zn = 0;
}
if(*(pv+(top->v)) !=MIN)
{
*(pu+(top->u))=(top->b) - *(pv+(top->v));
fl=1;
top->zn = 0;
}
}
}
if(!fl) break;
}
printf("\n ÏÎÒÅÍÖÈÀËÛ ÏÎ v:");
fprintf(fil,"\n **** ÏÎÒÅÍÖÈÀËÛ ÏÎ v:");
for(i = 0;i<n;i++)
{
printf("%d",*(pv+i));
fprintf(fil,"%5d",*(pv+i));
}
getch();
printf("\n ÏÎÒÅÍÖÈÀËÛ ÏÎ u: ");
fprintf(fil,"\n **** ÏÎÒÅÍÖÈÀËÛ ÏÎ u: ");
for(i=0;i<m;i++)
{
printf("%d",*(pu+i));
fprintf(fil,"%5d",*(pu+i));
}
fprintf(fil,"\n");
for(top = topnast;top!=NULL;top = top->next)
free(top);
return;
} // potenzial
// ****** PROVERKA PLANA NA OPTIMALNOST' ************************
void abcikl(int ik,int jk);
int cikl(int ik,int jk);
void pr(char pr[],void *st); // Ïðåäâàðèòåëüíî
int prpoisk(int i1,int j1); // Îáúÿâëåíû
int levpoisk(int i1,int j1); //ÝÒÈ
int verpoisk(int i1,int j1); //Ôóíêöèè
int nizpoisk(int i1,int j1);
int optim(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
// ÈÙÅÌ ÎÏÒÈÌÀËÜÍÎÅ ÐÅØÅÍÈÅ Â ÍÀØÅÉ ÌÀÒÐÈÖÅ È ÅÑËÈ ÅÃÎ ÍÅ ÍÀÉÄÅÌ
// ÒÎ ÏÎ ÑËÅÄÓÞÙÅÌÓ ÓÑËÎÂÈÞ ÏÐÈÑÂÎÈÌ ÃÐÀÔÎÊËÅÒÊÅ Ñ ÊÎÎÐÄÈÍÀÒÀÌÈ
// ik,jk ÇÍÀ×ÅÍÈÅ -1
if(( *(pu+i)+ *(pv+j))>(*(st+i*n+j))&&((*(matr+i*n+j)) == 0))
{
abcikl(i,j);
fprintf(fil,"optim(): Ïëàí íå îïòèìàëåí, ôóíêöèè main() âîçâðàùàåì -1,\n à abcikl() ïàðàìåòðû i,j ");
return(-1);
}
}
}
fprintf(fil,"Plan optimalen");
return(0);
} // ******* optim() ***************
// ************** UPGRADE PLAN **************************
void abcikl(int ik,int jk)
{
int i,j;
fprintf(fil,"Ìû â abcikl()");
if((matr2=(int*)calloc(n*m,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
*(matr2+i*n+j) = *(matr+i*n+j); // Ñîçäàåì êîïèþ ðàáî÷åé ìàòðèöû
}
}
*(matr2+ik*n+jk) = -1;
// çíà÷åíèþ ìàòðèöû ñ ïàðàìåòðàìè ik,jk ïðèñâàåâàåì -1
printf("\n");
printf("Ïîèñê Öåïè: \n\n");
fprintf(fil,"Ïîèñê Öåïè: \n\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr2+i*n+j));
printf("%5d",*(matr2+i*n+j));
}
fprintf(fil,"\n");
printf("\n");
}
fprintf(fil,"\n\n Ïåðåõîäèì â Ñðàíóþ, Ìàòü å¸, Ôóíêöèþ cikl(ik,jk) \n");
getch();
cikl(ik,jk);
return;
} // abcikl
// ********* FUNKCION POISKA CIKLA **************************
int cikl(int ik,int jk)
{
int nst,nstr,i,j,
perlev = 0,
perpr = 0;
int perver = 0,
perniz = 0,
fl = 0,
fl3 = 1;
int napr;
struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *topnast1 = NULL,
*top2 = NULL,
*top3 = NULL;
ch = 0;
if((top2 = (struct cik*)malloc(sizeof(struct cik))) == NULL)
abort();
if(!topnast1)
{
topnast1=top2;
top3=top2;
top3->ick=ik;
top3->jck=jk;
}
else
top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
fprintf(fil,"\n\nÄî Óñëîâèÿ while fl3 =%d \n",fl3);
pr("top2",top2);
fprintf(fil,"Âåñü öèêë ïîèñêà ñåé÷àñ íà÷íåòñÿ, íàäåþñü - \n ÷òî îí áóäåò íå áåñêîíå÷íûé èëè íå áåñïîëåçíûé :( \n");
printf("Âåñü öèêë ïîèñêà ñåé÷àñ íà÷íåòñÿ, íàäåþñü - \n ÷òî îí áóäåò íå áåñêîíå÷íûé èëè íå áåñïîëåçíûé :( \n");
printf("\n \t \t\tpress anykey to contunio\n");
getch();
while(fl3)
{
fl3=0;
fl = 0;
if((nst = prpoisk(ik,jk))>=0)
{
fprintf(fil,"\n\nÂíèìàíèå!!!\n nst = %d \n",nst);
fprintf(fil,"Ùà áóäåò ïîèê èäòè åìó áû...:Point found!\n");
printf("È îí ïîøåë RIGHT:Point found !\n\r");
napr = 2;
jk = nst;
top2->prnapr = 1;
}
else if((nstr = nizpoisk(ik,jk))>=0)
{
fprintf(fil,"DOWN: Point found !\n");
printf("DOWN: Point found !\n\r");
napr = 3;
ik = nstr;
top2->prnapr = 2;
}
else if((nst=levpoisk(ik,jk))>=0)
{
fprintf(fil,"LEFT:Point found !\n");
printf("LEFT:Point found !\n\r");
napr = 4;
jk = nst;
top2->prnapr = 3;
}
// **************** Prodolzhenie 1 poiska ***********************
else if((nstr = verpoisk(ik,jk))>=0)
{
fprintf(fil,"UP:Point found !\n");
printf("UP:Point found !\n\r");
napr = 1;
ik = nstr;
top2->prnapr = 4;
}
else
return(-1);
while(!fl || *(matr2+ik*n+jk)!=-1)
{
fl=1;
switch(napr)
{
case 1:
printf("Search to the right --->");
fprintf(fil,"Search to the right --->");
if((nst = prpoisk(ik,jk))>=0)
