#include <vcl.h>
#pragma hdrstop
#include <iostream.h>
#include <math.h>
#include <conio.h>
#include <stdio.h>

#pragma argsused

/*-----------------------------------------------------------------------------
                               Алгоритм
 цикл Napr
  цикл BMatExp
     выделить минимальный элемент
     запретить строку и столбец, в котором находится этот элемент
     занести минимальный элемент в сумму
     найти следующий незапрещенный минимальный элемент
  повторять пока вся таблица не будет запрещена
 повторить алгоритм для разных начальных элементов
выбрать минимальную сумму
-----------------------------------------------------------------------------*/
void main(void)
{ const int n=5;                                          //MA--Mex      AM--Ak

  float MA[n], AM[n];
  char* MAdd[n][n];                                       //живет в этом городе + маршруты по координатам
  float Mex[n][n],  Ak[n][n],   Mat[n][n];
  bool  BMat[n][n], BMatExp[n][n], Napr[n][n], Graf[n][n], GrafExp[n][n], fl, exit;
  int   i, j, x, y, kolich;
  float sum, SUMMA, min;

  MA[0]=6;    MA[1]=7.5; MA[2]=11.5; MA[3]=19;    MA[4]=0.5;     //время выезда из Мехико
  AM[0]=5.5;  AM[1]=9;   AM[2]=15;   AM[3]=18.5;  AM[4]=0;       //время выезда из Акапулько

  for (i=0; i<n; i++)
       for (j=0; j<n; j++)
          {    Mex[j][i]=MA[j]-(AM[i]+6);                 //расчет времени ожидания в Мехико + транспонирование
               while( Mex[j][i]<0 ) {Mex[j][i]+=24;}      //избавление от отрицательных элементов
               Ak[i][j]=AM[j]-(MA[i]+6);                  //расчет времени ожидания в Акапулько
               while( Ak[i][j]<0 ) {Ak[i][j]+=24;}        //избавление от отрицательных элементов
          }

  for (i=0; i<n; i++)                                     //выборка минимальных элементов
        for (j=0; j<n; j++)                                //и создания матрицы ожидания в городах
            {
                if (Mex[i][j]<4) {Mat[i][j]=Ak[i][j]; MAdd[i][j]="Mexico";}
                else  if (Ak[i][j]<4) {Mat[i][j]=Mex[i][j]; MAdd[i][j]="Akapulco";}
                      else if (Mex[i][j]<Ak[i][j]) {Mat[i][j]=Mex[i][j]; MAdd[i][j]="Akapulco";}
                           else {Mat[i][j]=Ak[i][j]; MAdd[i][j]="Mexico";}
            }
SUMMA=n*24;                                              //сумма минимальных элементов
  for (i=0; i<n; i++)                                    //создание таблиц для расчета
        for (j=0; j<n; j++)
        {     if (Mat[i][j]<4) {BMat[i][j]=false; Napr[i][j]=false;}
              else             {BMat[i][j]=true;  Napr[i][j]=true;}
              Graf[i][j]=false;
        }
//------------------------------------------------------------------------
exit=true;
   while (exit)                                     //цикл для Napr
   {    sum=0;                                      //текущая сумма минимальных элементов
        kolich=0;                                   //количество найденных минимальных элементов
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)                     //создание текущих таблиц
            {    BMatExp[i][j] = BMat[i][j];
                 GrafExp[i][j] = false;
            }
        min=24;                                     //текущий минимальный элемент
        for (i=0; i<n; i++)                         //определение минимального элемента матрицы
            for (j=0; j<n; j++)                       //и его координат
                if ((Napr[i][j])&&(BMatExp[i][j])&&(min>Mat[i][j]))
                      {min=Mat[i][j];  x=i;  y=j;}
        for (int k=0; k<n; k++)
        {   BMatExp[x][k]=false;                    //запрещаем строку и столбец
            BMatExp[k][y]=false;                    //минимального элемента
        }
        Napr[x][y]=false;                         //запрещение элемента
        GrafExp[x][y]=true;                       //отметка минимального элемента для вывода
        sum+=Mat[x][y];                           //текущая сумма минимальных элементов
        kolich++;                                 //количество минимальных элементов в текущей сумме
        fl=false;
        for (i=0; i<n; i++)                       //проверка охваченных элементов
           for (j=0; j<n; j++)
              if (BMatExp[i][j]) {fl=true;}
//-----------------------------------------------------------------------------
        while (fl)                               //цикл для BMatExp
        {   min=24;                              //текущий минимальный элемент
            for (i=0; i<n; i++)                  //поиск минимального элемента и его координат
                for (j=0; j<n; j++)
                    if ((BMatExp[i][j])&&(min>Mat[i][j]))
                         {min=Mat[i][j]; x=i; y=j;}
            for (int k=0; k<n; k++)              //запрещение строки и столбца
            {                                      //минимального элемента
                BMatExp[x][k]=false;
                BMatExp[k][y]=false;
            }
            sum+=Mat[x][y];                      //текущая сумма минимальных элементов
            GrafExp[x][y]=true;
            kolich++;                            //количество минимальных элементов
            fl=false;
            for (i=0; i<n; i++)                  //проверка охваченных элементов
                for (j=0; j<n; j++)
                    if (BMatExp[i][j]) {fl=true;}
        }                                        //конец цикла для BMatExp
        if ((kolich==n)&&(SUMMA>sum))             //определение минимальной суммы
        {   SUMMA=sum;                             //с пятью слагаемыми
            for (i=0; i<n; i++)                    //и занесение их в таблицу вывода
               for (j=0; j<n; j++)
                  Graf[i][j]=GrafExp[i][j];
        }
        exit=false;                            //проверка охвата сумм для
        for (i=0; i<n; i++)                     //всех элементов
            for (j=0; j<n; j++)
                if (Napr[i][j]) exit=true;
   }                                           //конец цикла для Napr
//---------Вывод на экран----------------------------------------------------
cout<<"Waiting in Mexico"<<endl;
  for  (i=0; i<n; i++)                         //матрица времени ожидания в Мехико
       {for (j=0; j<n; j++)
            printf("%5.1f ",Mex[i][j]);
        cout<<endl;
       }
cout<<endl;
cout<<"Waiting in Akapulco"<<endl;
  for  (i=0; i<n; i++)                         //матрица времени ожидания в Акапулько
       {for (j=0; j<n; j++)
            printf("%5.1f ",Ak[i][j]);
        cout<<endl;
       }
cout<<endl;
cout<<"Waiting"<<endl;
  for  (i=0; i<n; i++)                         //вывод общей матрицы времени ожидания
       {for (j=0; j<n; j++)
            printf("%5.1f ",Mat[i][j]);
        cout<<endl;
       }
cout<<endl;
cout<<"Elements as table"<<endl;
  for  (i=0; i<n; i++)                  //вывод искомых элементов
       {for (j=0; j<n; j++)
            cout<<"   "<<Graf[i][j]<<"  ";
        cout<<endl;
       }
cout<<endl;
  for (i=0; i<n; i++)                  //вывод искомых элементов
         for (j=0; j<n; j++)
             if (Graf[i][j])
              {    cout<<"Brigada "  <<i+1    <<" s reysami "
                       << i          <<" from Akapulco and "
                       << j          <<" from Mexico must lives in "
                       << MAdd[i][j] <<endl;
              }
  cout<<"Min waiting time is "<<SUMMA;
  getch();
}
//---------------------------------------------------------------------------