*(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("\n");
fprintf(fil,"\n");
}
fprintf(fil,"********************\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("\n Rezultat : %d",rez);
printf("\n");
fprintf(fil,"%s %5d"," Rezultat : ",rez);
fprintf(fil,"\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("\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)
{
printf("founded\n\r");
fprintf(fil,"founded\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\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\n\r"); fprintf(fil,"founded\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\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\n\r"); fprintf(fil,"founded\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\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\n\r"); fprintf(fil,"founded\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\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\n\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\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d)=%d\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\n\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\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d) = %d\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("\n\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\n\r",ptr->ick,ptr->jck);
fprintf(fil,"and napravlenie");
printf("Napravlenie");
switch(ptr->prnapr)
{
case 1:
fprintf(fil,"Vpravo\n");
printf("Vpravo\n\r");
break;
case 2:
fprintf(fil,"Vniz\n");