Метод потенциалов в транспортной задаче - C++ - Ответ 7460059

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
int ii, jj, I, J, teta;
int u[100], v[100];
int kp,kpo;
int a[10];  // запасы поставщиков
int b[10];  // потребности потребителей
int mat[10][10]; // цены перевозок
int SprosOst[10], PredlOst[10],volume;
int gener;
struct kletka
{
    bool bas;   // 1 - ячейка базисная, 0 - свободная
    int mat;    // цена перевоза
    int c;      // потенциал свободной ячейки
    int uu;     // потенциал по строке
    int vv;     // потенциал по столбцу
    int otgruz; // сколько отгруз
};
kletka massiv[10][10];
 
void opornui_plan() // составление опорного плана методом сверо-западного угла для задачи
{
    int i,j;
    for(j=0 ;j< kpo;j++)
        SprosOst[j]=b[j];
    for(i=0 ;i< kp;i++)
        PredlOst[i]=a[i];
    for(i=0 ;i< kp;i++)
    {
        for( j=0 ;j< kpo;j++)
        {
            massiv[i][j].bas=0;
            massiv[i][j].otgruz=0;
        }
    }
    for( i=0 ;i< kp;i++)
    {
        for (j=0 ;j< kpo;j++)
        {
            if (PredlOst[i]==0)
                break;
            else if (PredlOst[i]<0)
                cout<<endl<<"Error"<<endl;
            volume=SprosOst[j];
            if (volume==0)
                continue;
            else if (volume<0)
                cout<<endl<<"Error"<<endl;
            if (PredlOst[i]<volume)
                volume=PredlOst[i];
            SprosOst[j]=SprosOst[j]-volume;
            PredlOst[i]=PredlOst[i]-volume;
            massiv[i][j].bas=1;
            massiv[i][j].otgruz=volume;
        }
    }
}
 
void potencial_po_stolbcu(int j);
 
void potencial_po_stroke(int i)
{int j;
     gener=gener-1;
     if (gener==0)
         cout<<"Erere"<<endl;
 
     if (u[i]==1000)
         cout<<"Erpol"<<endl;
 
     for (j=0 ; j<kpo;j++) {
         if (massiv[i][j].bas==0)
             continue;
 
         if (v[j]!=1000)
             continue;
         else
         { v[j]=massiv[i][j].mat-u[i];
             potencial_po_stolbcu(j);
         }
     }
 }
bool potencial() // вычисление потенциалов
{    int i, j, schet;
     int v[100],u[100];
     for(i=0 ;i< kp;i++) {
         u[i]=1000;
     }
 
     for(j=0 ;j< kpo;j++) {
         v[j]=1000;
     }
     u[0]=0;
     schet=kp*kpo; // Максимальное число итераций
     potencial_po_stroke(1); //Начало рекурсии
     //Проверка
     for(i=0 ;i< kp;i++) {
         if (u[i]==1000)
             cout<<"Could not calculate"<<endl;
             return 0;
         }
     for (j=0 ;j<kpo;j++) {
         if (v[j]==1000)
             cout<<"Not"<<endl;
             return 0;
 
     }
     return 1;
 }
 
void potencial_po_stolbcu(int j)
{ int i;
     if (v[j]==1000)
         cout<<"Errorrrr"<<endl;
 
     for (i=0 ;i< kp;i++) {
         if (massiv[i][j].bas==0)
             continue;
 
         if (u[i]!=1000)
             continue;
         else
         {u[i]=massiv[i][j].mat-v[j];
             potencial_po_stroke(i);
         }
     }
}
 
 
 
 
int check_optim()
{ int i1,j1;
    int hResOpt, mindelta, i, j, Deltta;
    hResOpt=1;
    mindelta=1000;
    for(i=0;i< kp;i++){
        cout<<"Deltta="<<cout;
        for(j=0; j< kpo;j++) {
            if ( massiv[i][j].bas==1 )
                Deltta=0;
            else
                Deltta = massiv[i][j].mat-u[i]-v[j];
            if ( Deltta<0 )
                hResOpt=0;
 
            if ( mindelta==1000 ) {
                mindelta=Deltta;
                i1=i;
                j1=j;}
            else
                if ( Deltta<mindelta ) {
                    mindelta=Deltta;
                    i1=i;
                    j1=j;
                }
 
        }
    }
    return hResOpt;
}
 
// Если решение вырождено, то надо ввести в число базисных переменную с нулевой отгрузкой
bool Find_nol_kletka()
{ int i,j;
    //Проверка
    bool ok=0;
    for(i=0;i< kp;i++) {
        for(j=0;j< kpo;j++) {
            if ( massiv[i][j].bas==0 ) {
                ok=1;
                break;
            }}
 
        if ( ok==1 )
            break;}
    if ( ok==0 )
        cout<<"Net nol kletka"<<endl;
 
    while (1) {
 
        int i=rand()% kp;
        int j=rand() % kpo;
 
        if ( massiv[i][j].bas==1 )
            //Пропускаем базисные ячейки
            continue;
 
        if ( massiv[i][j].otgruz!=0 )
            cout<<"Ne null otgr"<<endl;
 
        massiv[i][j].bas=1;
        ii=i;
        jj=j;
        cout<<"VVEDENA KLETKA "<<i+1<<" , "<<j+1<<endl;
        return 1; //Удалось ввести ячейку в базис
    }
}
//Поиск цикла для перераспределения поставок.
//Заполняет массивы iЦикл и jЦикл с координатами вершин цикла.
//Возвращает 1, если цикл найден и 0, если не удалось найти цикл.
bool find_po_stolbcu();
bool find_po_stroke();
bool find_cikl()
{
    int i,j, general;
   general= kp*kpo; // максимальное число итераций
    for(i=0;i<kp;i++)
    if (find_po_stroke()==1) break;
    for(j=0;j<kpo;j++)
    if (find_po_stolbcu()==1 ) break;
        return 1; //Цикл найден успешно
    return 0;//Цикл не найден
}
 
bool find_po_stroke()
{
            if (massiv[ii][jj].bas==1) {I=ii; return 1;} else return 0;
}
 
bool find_po_stolbcu()
{
            if (massiv[ii][jj].bas==1) { J=jj; return 1;} else return 0;
}
 
//Перераспределение объемов отгрузки по найденному циклу iЦикл, jЦикл
bool exchange()
{int i,j;
    cout<<endl<<"Pereraspredelenie "<<endl;
    teta=1000;
    bool znak=1;
    for(i=0; i<kp; i++) {
        find_cikl();
        if ( znak==0 ) {
            volume=massiv[i][j].otgruz;
            if ( teta==1000 )
                teta=volume;
            else
                if ( volume<teta )
                    teta=volume;
            znak=1;
        }
        else
            znak=0;
 
    }
    if ( teta=1000 )
        cout<<"Not teta"<<endl;
    cout<<"Тета= "<<teta<<endl;
    if ( teta==0 )
        return 0;
    znak=1;
    for(i=0; i<kp;i++) {
        find_cikl();
        if (znak==0 ) {
            massiv[i][j].otgruz-=teta;
            znak=1; }
        else {
            massiv[i][j].otgruz+=teta;
            znak=0;
        }
    }
   return 1;
}
 
 
int main()
{
    int i=0,j=0;
    bool res;
    cout<<"Enter kolichestvo postavshikov"<<endl;
    cin>>kp;
    cout<<endl<<"Enter zapasy postavshikov"<<endl;
    for(i=0;i<kp;i++)
        cin>>a[i];
    cout<<endl<<"Enter kolichestvo potrebiteley"<<endl;
    cin>>kpo;
    cout<<endl<<"Enter potrebnosty potrebiteley"<<endl;
    for(i=0;i<kpo;i++)
        cin>>b[i];
    int cleanSpros=0;
    for (j=0;j<kpo;j++) {
        cleanSpros+=b[j];
    }
    int cleanPredl=0;
    for (i=0; i< kp;i++) {
        cleanPredl+=a[i];
    }
 
    if (cleanPredl>cleanSpros)
    { cout<<endl<<"Please, enter not existining potrebitel"<<endl;
        return 0; }
    else if (cleanPredl<cleanSpros) {
        cout<<endl<<"Predlos < sprosa"<<endl;
        return 0;
    }
    cout<<endl<<"Enter ceny perevozok"<<endl;
    for(i=0;i<kp;i++)
        for(j=0;j<kpo;j++)
            cin>>massiv[i][j].mat;
    for(i=0;i<kp;i++)   // обнуляем ячейки по отгрузу и базисности
        for(j=0;j<kpo;j++)
        {
            massiv[i][j].bas=0;
            massiv[i][j].otgruz=0;
        }
 
    opornui_plan(); // составляется опорный план
 
    cout<<endl;
    for(i=0;i<kp;i++){
        for(j=0;j<kpo;j++)
        {
            cout.width(5);
            cout<<massiv[i][j].bas;
        }
        cout<<endl;}
        cout<<endl<<endl;
        for(i=0;i<kp;i++){
            for(j=0;j<kpo;j++)
            {
                cout.width(5);
                cout<<massiv[i][j].mat;
            }
            cout<<endl;}
            cout<<endl<<endl;
            for(i=0;i<kp;i++){
                for(j=0;j<kpo;j++)
                {
                    cout.width(5);
                    cout<<massiv[i][j].otgruz;
                }
                cout<<endl;}
            int sum=0;     // сумма цен пути обнуляется
            for(i=0;i<kp;i++) // расчет и вывод суммы цен пути
            {
                for(j=0;j<kpo;j++)
                sum+=massiv[i][j].otgruz*massiv[i][j].mat;
            }
            cout<<"Summa puti po opornomu plany "<<sum<<endl;
int volBas;
            while (1) {
                    volBas=0;
                    for (i=0;i< kp;i++)
                        for (j=0;j<kpo;j++)
                            if (massiv[i][j].otgruz>0)
                                volBas+=1;
 
                    while (volBas<(kp+kpo-1)) {
                        cout<<endl<<"Reshenie vyroshdeno"<<endl;
                        Find_nol_kletka();
                        volBas+=1;
                    }
cout<<endl<<endl<<"------ "<<ii<<" "<< jj<<endl;
for(i=0;i<kp;i++){
    for(j=0;j<kpo;j++)
    {
        cout.width(5);
        cout<<massiv[i][j].bas;
    } cout<<endl; }
 
 
                    if (potencial()==0)
                        continue;
                    if (check_optim()==1) {
                        cout<<endl<<"OPTIM"<<endl;
                        break;   // решение оптимально и нужно прервать
                    }
                    cout<<endl<<"Not optim"<<endl;
                    if (find_cikl()==0)
                        cout<<endl<<endl<<"Cikl not found";
                    exchange();
                    sum=0;     // сумма цен пути обнуляется
                                for(i=0;i<kp;i++) // расчет и вывод суммы цен пути
                                {
                                    for(j=0;j<kpo;j++)
                                    sum+=massiv[i][j].otgruz*massiv[i][j].mat;
                                }
                                cout<<"Summa puti po OPTIM plany "<<sum<<endl;
                }
                return 0;
 
 
 
}