//Algorytm Balas'a
//www.algorytm.org

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define INF 1000000;

using namespace std;

typedef std::vector< std::vector<int> > MVector;

/* Funkcja pozwalajaca przeksztalcic dowolne zadanie (maksymalizacyjne badz minimalizacyjne)
 * z dowolnymi ograniczeniami (wieksze rowne lub mniejsze rowne) do postaci pozwalajacej
 * rozwiazanie zadania za pomoca algorytmu Balas'a
 *
 * Dane wejsciowe:
 * N - liczba zmiennych
 * M - liczba ograniczen
 * A - macierz wspolczynnikow
 * B - wektor ograniczen
 * C - wektor wartosci funkcji celu
 * O - wektor okreslajacy rodzaj ograniczen (mniejsze rowne - 0, wieksze rowne - 1)
 * MAX - zmienna logiczna okreslajaca czy zadanie jest sformulowane jako maksymalizacyjne - true
         badz minimalizacyjne - false
 */
void PrepareBalas(unsigned int N, unsigned int M, int** A, int* B, int* C, int* O, bool MAX)
{
  // Ustawienie wszystkich ograniczen na mniejsze rowne
  for(unsigned int i=0; i<M; i++)
  {
    if(O[i]>0) // Jesli ograniczenie wieksze rowne mnozymy przez -1
    {
     for(unsigned int j=0;j<N;j++)
       A[i][j]=-A[i][j];
     B[i]=-B[i];
    }
  }

  // Zmiana problemu maksymalizacji na problem minimalizacji
  if(MAX)
  {
    for(unsigned int j=0;j<N;j++)
    {
      C[j]=-C[j];
      if(C[j]<0)
      {
	for(unsigned int i=0; i<M; i++)
	{
	  A[i][j]=-A[i][j];
	  B[i]=B[i]+A[i][j];
	}
      }
    }
  }

}

/* Funkcja realizujaca algorytm Balas'a
 *
 * Dane wejsciowe:
 * N - liczba zmiennych
 * M - liczba ograniczen
 * A - macierz wspolczynnikow
 * B - wektor ograniczen
 * C - wektor wartosci funkcji celu
 */
bool Balas(unsigned int N, unsigned int M, int** A, int* B, int* C)
{

  std::vector<int> X(N), XX(N), U(N), Y(M), V(N), T;

  MVector MT(N, std::vector<int>(0));

  int FVAL=INF;
  int Z=0, YMIN, SUM, R;
  bool EXIST=false;
  bool FLAGUE;


  // Wyzerowanie początkowych zmiennych
  for(unsigned int j=0; j<N; j++)
  {
    X[j]=0;
    U[j]=0;
    XX[j]=-1;
  }

  // Petla glowna algorytmu
  while(true)
  {
  // Petla algorytmu nie zawierajaca kroku 6-tego
    while(true)
    {
      // Krok 2
      for(unsigned int i=0; i<M; i++)
      {
	Y[i]=B[i];
	for(unsigned int j=0;j<N; j++)
	{
	  if(XX[j]>0)
	    Y[i]=Y[i]-A[i][j]*XX[j];
	}
      }
      YMIN=*(min_element(Y.begin(), Y.end()));

      Z=0;
      for(unsigned int j=0;j<N; j++)
      {
	if(XX[j]>0)
	  Z=Z+C[j]*XX[j];
      }

      if(YMIN>=0 && Z<FVAL)
      {
	X=XX;
	FVAL=Z;
	EXIST=true;
	break;
      }

      // Krok 3
      T.clear();
      for(unsigned int j=0; j<N; j++)
      {
	for(unsigned int i=0;i<M; i++)
	{
	  if(XX[j]<0 && A[i][j]<0 && Z+C[j]<FVAL && Y[i]<0)
	  {
	    T.push_back(j);
	    break;
	  }
	}
      }
      if(T.size()==0)
	break;

      // Krok 4
      FLAGUE=false;
      for(unsigned int i = 0; i < M; i++)
      {
	if(Y[i]<0)
	{
	  SUM=0;
	  for(unsigned int j = 0; j < T.size(); j++)
	    SUM=SUM+min(0, A[i][T[j]]);

	  if(Y[i]-SUM<0)
	  {
	    FLAGUE=true;
	    break;
	  }
	}
      }
      if(FLAGUE==true)
	break;

      // Krok 5
      MT.clear();
      FLAGUE=false;
      for(unsigned int j = 0; j < N; j++)
      {
	for(unsigned int i = 0; i < M; i++)
	{
	  if(Y[i]-A[i][j]<0)
	    MT[j].push_back(i);
	}

	V[j]=0;
	for(unsigned int i = 0; i < MT[j].size(); i++)
	  V[j]=V[j]+Y[MT[j][i]]-A[MT[j][i]][j];

	if(MT[j].size()>0)
	  FLAGUE=true;
      }
      if(FLAGUE==false)
	break;

      FLAGUE=false;
      for(unsigned int j = 0; j < N; j++)
      {
	if(V[j] >= *(max_element(V.begin(), V.end())))
	{
	  XX[j]=1;
	  for(unsigned int k=0; k<N; k++)
	    if(U[k]==0)
	    {
	      U[k]=j;
	      break;
	    }

	  FLAGUE=true;
	  break;
	}
      }
      if(FLAGUE==false)
	break;

    }

    // Krok 6
    R=-1;
    for(int k=N-1; k>=0; k--)
    {

      if(U[k]>0)
      {
	XX[U[k]]=0;
	U[k]=-U[k];
	R=k+1;
	break;
      }
    }
    if(R<0)
      break;
    for(unsigned int k=R; k<N; k++)
      U[k]=0;
  }
  if(EXIST)
  {
    cout << "x = (";
    for(unsigned int i=0; i<N; i++)
    {
      if(X[i]<0)
	X[i]=0;
      cout << X[i];
      if(i==N-1)
	cout << ");";
      else
	cout << ",";
    }
    cout << endl;
    cout << "Function value: " << FVAL << endl;
  }
return EXIST;
}

int main()
{
  unsigned int N=4;
  unsigned int M=3;
  int** A = new int*[M];
  int* B = new int[M];
  int* C = new int[N];

  for(unsigned int i=0; i<M; i++)
    A[i] = new int[N];

  // Przykladowy problem
  C[0]=10; C[1]=14; C[2]=21; C[3]=42;
  B[0]=-12; B[1]=-14; B[2]=-10;
  A[0][0]=-8; A[0][1]=-11; A[0][2]=-9; A[0][3]=-18;
  A[1][0]=-2; A[1][1]=-2; A[1][2]=-7; A[1][3]=-14;
  A[2][0]=-9; A[2][1]=-6; A[2][2]=-3; A[2][3]=-6;

  /* Zmienić na N=5
  C[0]=5; C[1]=7; C[2]=10; C[3]=3; C[4]=1;
  B[0]=-2; B[1]=0; B[2]=-1;
  A[0][0]=-1; A[0][1]=3; A[0][2]=-5; A[0][3]=-1; A[0][4]=4;
  A[1][0]=2; A[1][1]=-6; A[1][2]=3; A[1][3]=2; A[1][4]=-2;
  A[2][0]=0; A[2][1]=1; A[2][2]=-2; A[2][3]=1; A[2][4]=1;*/


  // Tablica zawierająca informację, czy ograniczenie jest:
  // 0 - mniejsze równe B[i]
  // 1 - większe równe B[i]
  int* O = new int[M];
  O[0]=0; O[1]=0; O[2]=0;


  // Wywolanie przygotowania algorytmu
  PrepareBalas(N, M, A, B, C, O, false);

  // Wywolanie algorytmu
  Balas(N, M, A, B, C);


  // Zwolnienie dynamicznej pamieci
  for(unsigned int i=0; i<M; i++)
    delete A[i];
  delete B;
  delete C;

  return (0);
}