Смекни!
smekni.com

Транспортная задача (стр. 2 из 3)

*(po+i)=0;

break;

}

*(matr+i*n+j)=*(pn+j);

*(po+i) -= *(pn+j);

*(pn+j)=0;

ch1++;

}

}

//********* ПРОВЕРКА И ВЫвод получившейся матрицы ***********************

printf("PROVERKA\n");

fprintf(fil,"PROVERKA MATRIX - Северо заподный УГОЛ,\n просмотр получившегося распределения в матрице \n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

printf("%5d",*(matr+i*n+j));

fprintf(fil,"%d",*(matr+i*n+j));

}

printf("&bsol;n");

fprintf(fil,"&bsol;n");

}

fprintf(fil,"********************&bsol;n");

return;

} // opplan

void kost(void)

{

int i,j, *matr1,rez=0;

//выделение памяти

if((matr1=(int*)calloc(n*m,sizeof(int))) == NULL) abort();

//присвоение новой матрице значения базисной(старой) матрицы

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

*(matr1+i*n+j) = *(matr+i*n+j);

}

}

// Подсчет стоимости базисной матрицы (созданного массива)

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if(*(matr1+i*n+j)>0)

rez += (*(matr1+i*n+j)) *(*(st+i*n+j));

}

}

printf("&bsol;n Rezultat : %d",rez);

printf("&bsol;n");

fprintf(fil,"%s %5d"," Rezultat : ",rez);

fprintf(fil,"&bsol;n");

getch();

free(matr1);

if(zen == rez)

{

z=0;

}

zen = rez;

return;

}

//************* KOST()

//************* PODSCHET POTENCIALOV ********************

void potenzial(void)

{

struct poten

{

int v;

int u;

int zn;

struct poten *next;

int b;

} *topnast = NULL,

*top = NULL,

*top1 = NULL;

int i,j;

int fl;

//********** ВЫДЕЛЕНИЕ ПАМЯТИ *******************8

if((pu=(int*)calloc(m,sizeof(int)))==NULL) abort();

if((pv=(int*)calloc(n,sizeof(int)))==NULL) abort();

// ПРИСВОЕНИЕ ВСЕМ ПОТЕНЦИАЛАМ ЗНАЧЕНИЯ MIN

for(i=0;i<m;i++)

*(pu+i) = MIN;

for(j=0;j<n;j++)

*(pv+j) = MIN;

// Выделение памяти под структуру и заполнение её значениями

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if((*(matr+i*n+j) > 0) || (*(matr+i*n+j)==-2))

{

if((top=(struct poten*)malloc(sizeof(struct poten)))==NULL)

abort();

fprintf(fil,"top = %d",top);

if(!topnast){

topnast = top;

fprintf(fil,"topnast = top = %d",top);

}

else top1 -> next=top;

top1=top;

top -> next=NULL;

top -> b = *(st+i*n+j); //Стоимости

top -> v = j;

top -> u = i;

top -> zn = -1;

}

}

}

*pu = 0;

i=0; j = -1;

for(top = topnast;top!=NULL;top = top -> next)

{

if((top -> u) == i && (top -> v)!=j)

{

*(pv+(top -> v)) = (top -> b) - *(pu+i);

j = (top->v);

top -> zn = 0;

}

else{

for(top1 = topnast;top1 != NULL;top1 = top1->next)

{

if((top1->v) == j && (top1->u)!=i)

{

*(pu+(top1->u))=(top1->b) - *(pv+j);

i = (top1->u);

top1 ->zn = 0;

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("&bsol;n ПОТЕНЦИАЛЫ ПО v:");

fprintf(fil,"&bsol;n **** ПОТЕНЦИАЛЫ ПО v:");

for(i = 0;i<n;i++)

{

printf("%d",*(pv+i));

fprintf(fil,"%5d",*(pv+i));

}

getch();

printf("&bsol;n ПОТЕНЦИАЛЫ ПО u: ");

fprintf(fil,"&bsol;n **** ПОТЕНЦИАЛЫ ПО u: ");

for(i=0;i<m;i++)

{

printf("%d",*(pu+i));

fprintf(fil,"%5d",*(pu+i));

}

fprintf(fil,"&bsol;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,&bsol;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("&bsol;n");

printf("Поиск Цепи: &bsol;n&bsol;n");

fprintf(fil,"Поиск Цепи: &bsol;n&bsol;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,"&bsol;n");

printf("&bsol;n");

}

fprintf(fil,"&bsol;n&bsol;n Переходим в Сраную, Мать её, Функцию cikl(ik,jk) &bsol;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,"&bsol;n&bsol;nДо Условия while fl3 =%d &bsol;n",fl3);

pr("top2",top2);

fprintf(fil,"Весь цикл поиска сейчас начнется, надеюсь - &bsol;n что он будет не бесконечный или не бесполезный :( &bsol;n");

printf("Весь цикл поиска сейчас начнется, надеюсь - &bsol;n что он будет не бесконечный или не бесполезный :( &bsol;n");

printf("&bsol;n &bsol;t &bsol;t&bsol;tpress anykey to contunio&bsol;n");

getch();

while(fl3)

{

fl3=0;

fl = 0;

if((nst = prpoisk(ik,jk))>=0)

{

fprintf(fil,"&bsol;n&bsol;nВнимание!!!&bsol;n nst = %d &bsol;n",nst);

fprintf(fil,"Ща будет поик идти ему бы...:Point found!&bsol;n");

printf("И он пошел RIGHT:Point found !&bsol;n&bsol;r");

napr = 2;

jk = nst;

top2->prnapr = 1;

}

else if((nstr = nizpoisk(ik,jk))>=0)

{

fprintf(fil,"DOWN: Point found !&bsol;n");

printf("DOWN: Point found !&bsol;n&bsol;r");

napr = 3;

ik = nstr;

top2->prnapr = 2;

}

else if((nst=levpoisk(ik,jk))>=0)

{

fprintf(fil,"LEFT:Point found !&bsol;n");

printf("LEFT:Point found !&bsol;n&bsol;r");

napr = 4;

jk = nst;

top2->prnapr = 3;

}

// **************** Prodolzhenie 1 poiska ***********************

else if((nstr = verpoisk(ik,jk))>=0)

{

fprintf(fil,"UP:Point found !&bsol;n");

printf("UP:Point found !&bsol;n&bsol;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)

{

printf("founded&bsol;n&bsol;r");

fprintf(fil,"founded&bsol;n");

if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)

abort();

if(!topnast1) topnast1=top2;

else top3 -> next=top2;

top3 = top2;

top2 -> next = NULL;

top2->ick = ik;

top2->jck = jk;

ch++;

top2->prnapr = 1;

pr("top2",top2);

napr = 2;

jk = nst;

perpr = perlev = 0;

} // **** IF *******

else

{

fprintf(fil,"Point not found ! Change direction to LEFT&bsol;n");

napr = 3;

perpr = 1;

}

break;

//***************** PRODOLZHENIE 2 POISKA ******************************

case 2:

printf("Search to the down --->");

fprintf(fil,"Search to the down --->");

if((nstr=nizpoisk(ik,jk))>=0)

{

if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)

abort();

printf("founded&bsol;n&bsol;r"); fprintf(fil,"founded&bsol;n");

if(!topnast1) topnast1=top2;

else top3->next=top2;

top3=top2;

top2->next=NULL;

top2->ick = ik;

top2->jck = jk;

ch++;

top2->prnapr = 2;

pr("top2",top2);

napr = 3;

ik = nstr;

perniz=perver=0;

} //**** IF ********

else

{

fprintf(fil,"Point not found ! Change direction to UP&bsol;n");

napr = 4;

perniz = 1;

}

break;

case 3:

printf("Search to the left -->");

fprintf(fil,"Search to the left -->");

if((nst=levpoisk(ik,jk))>=0)

{

if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL)

abort();

printf("founded&bsol;n&bsol;r"); fprintf(fil,"founded&bsol;n");

if(!topnast1)

topnast1=top2;

else

top3->next=top2;

top3=top2;

top2->next=NULL;

top2->ick = ik;

top2->jck = jk;

ch++;

//************ PRODOLZHENIE 3 POISKA *************

top2->prnapr = 3;

pr("top2",top2);

napr = 4; jk = nst;

perlev = perpr = 0;

} // ******* IF *****

else{

fprintf(fil,"Point not found ! Change direction to RIGHT&bsol;n");

napr = 1;

perlev = 1;

}

break;

case 4:

printf("Search to the up --->");

fprintf(fil,"Search to the up --->");

if((nstr=verpoisk(ik,jk))>=0)

{

if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)

abort();

printf("founded&bsol;n&bsol;r"); fprintf(fil,"founded&bsol;n");

if(!topnast1) topnast1=top2;

else top3->next=top2;

top3=top2;

top2->next=NULL;

top2->ick=ik;

top2->jck=jk;

ch++;

top2->prnapr = 4;

pr("top2",top2);

napr = 1;

ik = nstr;

perver = perniz = 0;

} // *****If **************

else

{

fprintf(fil,"Point not found ! Change direction to DOWN&bsol;n");

napr = 2;

perver = 1;

}

break;

} // ************ SWITCH ********************

// ************** PRODOLZHENIE 4 POISKA ********************

if(perlev == 1 && perpr == 1)

{

*(matr2+ik*n+jk) = 0;

ik = top3 ->ick;

jk = top3 ->jck;

napr = top3->prnapr;

top3 = topnast1;

printf("Zerro 1&bsol;n&bsol;r");

for(top2=topnast1;top2->next !=NULL;top2=top2->next)

top3 = top2;

top3 -> next=NULL;

perlev = perpr = 0; // if(ch == 1)

if(top2==top3)

{

fl3=1;

break;

}

else

{

top3->next=NULL;

free(top2);

ch--;

printf("Viynimaem tochky: (%d,%d)=%d&bsol;n",ik,jk,*(matr2+ik*n+jk));

fprintf(fil,"Viynimaem tochky: (%d,%d)=%d&bsol;n",ik,jk,*(matr2+ik*n+jk));

pr("top2",top2);

}

perpr = 0;

perlev = 0;

} // IF

if(perver == 1 && perniz == 1)

{

*(matr2+ik*n+jk)=0;

printf("Zerro 2&bsol;n&bsol;r");

ik=top3->ick;

jk = top3->jck;

napr = top3->prnapr;

top3 = topnast1;

for(top2 = topnast1;top2->next !=NULL;top2=top2->next)

top3 = top2; perver = perniz = 0;

if(top2==top3)

{

fl3=1;

break;

}

else

{

top3->next = NULL;

free(top2);

ch--;

// ******* PRODOLZHENIE 5 POISKA *********************

printf("Viynimaem tochky: (%d,%d) = %d&bsol;n",ik,jk,*(matr2+ik*n+jk));

fprintf(fil,"Viynimaem tochky: (%d,%d) = %d&bsol;n",ik,jk,*(matr2+ik*n+jk));

pr("top2",top2);

}

perver = 0;

perniz = 0;

} // IF

if(ch==0)

{

fl3=1;

break;

}

} //while

} //while

i=0;

if((zi = (int*)calloc(ch,sizeof(int))) == NULL ) abort();

if((zj = (int*)calloc(ch,sizeof(int))) == NULL ) abort();

printf("&bsol;n&bsol;r");

ch2 = ch;

for(top2 = topnast1;top2 !=NULL;top2 = top2->next)

{

*(zi+i) = top2 ->ick;

*(zj+i) = top2 ->jck;

i++;

}

return(0);

} // *********** cikl ****************************

int prpoisk(int i1, int j1)

{

int j;

for(j=j1+1;j<n;j++)

{

if((*(matr2+i1*n+j))!=0)

return(j);

}

return(-1);

}

int levpoisk(int i1,int j1)

{

int j;

for(j = j1-1;j>=0;j--)

{

if((*(matr2+i1*n+j))!=0)

return(j);

}

return(-1);

}

int verpoisk(int i1,int j1)

{

int i;

for(i=i1-1;i>=0;i--)

{

if((*(matr2+i*n+j1))!=0)

return(i);

}

return(-1);

}

int nizpoisk(int i1, int j1)

{

int i;

for(i = i1+1;i<m;i++)

{

if((*(matr2+i*n+j1))!=0)

return(i);

}

return(-1);

}

// ************* FUNCTION SEARCH ********************

void pr(char pr[],void *st)

{

struct cik { int prnapr;

int ick;

int jck;

struct cik *next;

} *ptr;

int i,j;

ptr = (struct cik *)st;

fprintf(fil,"Koordinatiy ytoplennoy tochki : %d and %d",ptr->ick,ptr->jck);

printf("Koordinatiy ytoplennoy tochki : %d and %d&bsol;n&bsol;r",ptr->ick,ptr->jck);

fprintf(fil,"and napravlenie");

printf("Napravlenie");

switch(ptr->prnapr)

{

case 1:

fprintf(fil,"Vpravo&bsol;n");

printf("Vpravo&bsol;n&bsol;r");

break;

case 2:

fprintf(fil,"Vniz&bsol;n");