#include <windows.h>
#include <process.h>
#include <memory.h>
#include <string.h>
//#include <fcntl.h>
#include <io.h>

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <dos.h>
#include <time.h>
#include <process.h>


const int maxRaiser = 11;

unsigned long uBound=0;
unsigned long lowerBound;
unsigned long MaxCost;
unsigned long NumCalls;
unsigned int foundsolution = 0;



int random2;
int random100;
FILE *NAME;

//structure to keep number of columns,used for solution
struct SetCols {
   unsigned int ColumnNumber;
   unsigned int ColumnCost;  // pridano kvuli vybrani sloupce ze SolCube s nejnizssi cenou
   struct SetCols *Next;
 };

//structure to keep number of rows,used for MSIR
struct SetRows {
   unsigned int Offset;
   unsigned int ID;     // 
   struct SetRows *Next;
 };

//structure to keep domains of covering matrix for Aura 
struct Cube {
  struct SetCols *SetC;
  struct Cube *Next;
  struct Cube *Previous;
};

//structure, where is kept linkt to set of columns included to solution
struct HeaderSol {
  unsigned int Cost;
  struct SetCols *SetC;//Link to set of columns
};

//structure, where is kept linkt to set of rows included to MSIR
struct HeaderSetRows {
   struct SetRows *RowsLink;
};

//structure where are kept row links an column links
struct CLink {
   struct CLink *Previous;
   struct CLink *Next;
   unsigned int ID;
   unsigned int Offset; //Offset to jump from one item to next
   unsigned int Cost;

   unsigned int NumberOf1;
   };
//structure where are kept colums for heuristics, that have the same score
//struct Columns {
//	struct CLink Column;
//	struct Columns *Next;
//};

//Structure where is kept the matrix
struct CoveringMatrix {
  struct CLink *RowLink;  //Link to rows of matrix
  struct CLink *ColLink;  //Link to columns of matrix
  unsigned int Cost;
  unsigned int Dirty;
  unsigned int M;        //Dimensions of matrix
  unsigned int N;
  unsigned char *Mat;    //Array
};



void Release (struct CoveringMatrix * CM)
{ //Function to release allocated memory for structure keeping matrix
  struct CLink *Aux;
  struct CLink *Aux2;

  if ( CM->ColLink !=0 )
    {//First,delete all rows
     Aux=CM->ColLink->Next;
    delete (CM->ColLink);
     while ( Aux!=0 )
      {
	Aux2=Aux->Next;
	delete (Aux);
	Aux=Aux2;
      }
    }
  if ( CM->RowLink !=0 )
    {//then delete all columns
     Aux=CM->RowLink->Next;
     delete (CM->RowLink);
     while ( Aux!=0 )
      {
	Aux2=Aux->Next;
	delete (Aux);
	Aux=Aux2;
      }
    }
  delete (CM);//fillany delete header of structure
}

void Release ( struct HeaderSetRows *HSR )
{ //structure to release allocated memory for MSIR
  struct SetRows *Aux;
  struct SetRows *Aux2;

  if ( HSR->RowsLink !=0 )
   {//delete all row links
      Aux=HSR->RowsLink->Next;
      delete ( HSR->RowsLink );
      while ( Aux!=0 )
	 {
	    Aux2=Aux->Next;
	    delete (Aux);
	    Aux=Aux2;
	 }
   }
   delete ( HSR );//delete header
}
void Release (struct SetCols *SetC){

	struct SetCols *Aux;
	struct SetCols *Aux2;
//	printf("zacinam uvolnovat");
	
	if (SetC!=0){
		Aux = SetC->Next;
		delete (SetC);
		while (Aux!=0){
			Aux2=Aux->Next;
			delete(Aux);
			Aux = Aux2;
		}
	}
//	delete (SetC);
//	printf("uvolneno       ");
}

void Release (struct Cube *SolCube) {

	struct SetCols *Aux;
	struct SetCols *Aux2;
	struct Cube *Auxx;
	struct Cube *Auxx2;

	Auxx = SolCube;
//	printf("ruseni start");
	
	while (Auxx->Next!=0){

		Auxx2 = Auxx->Next;
//		printf("hlavi cyklus ");

/*
		if ( Auxx->SetC !=0 )
		{//delete all column links
	     Aux=Auxx->Next->SetC;
		 delete (Auxx->SetC );
		 while ( Aux!=0 ){
		 Aux2=Aux->Next;
		 delete (Aux);
	     Aux=Aux2;
	     }
		}
*/		
		delete ( Auxx );
		Auxx = Auxx2;
//		printf("vymaz prvni kubiky   ");
	}
//	printf("yruseni uspesne XXXx \n");
}

void Releasex (struct Cube *SolCube) {

	struct SetCols *Aux;
	struct SetCols *Aux2;
	struct Cube *Auxx;
	struct Cube *Auxx2;

	Auxx = SolCube;
//	printf("ruseni start");
	while (Auxx->Previous != 0) Auxx = Auxx->Previous;
	
//	if (Auxx->SetC != 0){

	while (Auxx !=0){

		Auxx2 = Auxx->Next;
//		printf("hlavi cyklus ");
		
		if ( Auxx->SetC !=0 )
		{//delete all column links
	     Aux=Auxx->SetC->Next;
		 delete (Auxx->SetC );
		 while ( Aux!=0 ){
		 Aux2=Aux->Next;
		 delete (Aux);
	     Aux=Aux2;
	     }
		}

		
		delete ( Auxx );
		Auxx = Auxx2;
//		printf("vymaz prvni kubiky   ");
	}
//	delete (Auxx);
//Auxx->Next je nula

/*		if ( Auxx->SetC !=0 )
		{//delete all column links
	     Aux=Auxx->SetC->Next;
		 delete (Auxx->SetC );
		 while ( Aux!=0 ){
		 Aux2=Aux->Next;
		 delete (Aux);
	     Aux=Aux2;
	     }
		}
		delete ( Auxx );*/

	//else 
//	delete (Auxx->SetC);
	
	
//	printf("zruseni uspesne XXXx \n");
}


void Release ( struct HeaderSol *SolUCP )
{ //structure to release allocated memory for solution
  struct SetCols *Aux;
  struct SetCols *Aux2;
 
  if ( SolUCP->SetC !=0 )
   {//delete all column links
      Aux=SolUCP->SetC->Next;
      delete ( SolUCP->SetC );
      while ( Aux!=0 )
	 {
	    Aux2=Aux->Next;
	    delete (Aux);
	    Aux=Aux2;
	 }
   }
   delete ( SolUCP );//delete header
}


struct Cube *InitCube ( void )
{//Structure to create empty Cube
   struct Cube *Solution;
   //first allocate memory
   Solution = new Cube;
     if ( Solution==NULL)
       {
	printf ("Insufficient memory \n");
	exit(0);
       }
   //and set all antries to zero
   Solution->SetC=0;
   Solution->Next=0;
   Solution->Previous=0;

   return Solution;
}

struct HeaderSol *Init ( void )
{//Structure to create empty header structure to keep solution
   struct HeaderSol *Solution;
   //first allocate memory
   Solution=new HeaderSol;
     if ( Solution==NULL)
       {
	printf ("Insufficient memory \n");
	exit(0);
       }
   //and set all antries to zero
   Solution->Cost=0;
   Solution->SetC=0;

  return Solution;
}

struct SetCols *InitCols (void) {

	struct SetCols *Hlavicka;

	Hlavicka = new SetCols;
	if ( Hlavicka==NULL){
	printf ("Insufficient memory \n");
	exit(0);
    }
	
	Hlavicka->ColumnCost = 0;
	Hlavicka->ColumnNumber = 0;
	Hlavicka->Next = 0;
	

	return Hlavicka;
}

struct HeaderSetRows *InitSet ( void )
{//Structure to create empty header structure to keep rows of MSIR
   struct HeaderSetRows *Hlavicka;
   //first allocate memory
   Hlavicka=new HeaderSetRows;
     if ( Hlavicka==NULL)
       {
	printf ("Insufficient memory \n");
	exit(0);
       }
   //and set all antries to zero

   Hlavicka->RowsLink=0;
  return Hlavicka;
}
void Print ( struct CoveringMatrix *CM )
{//Print covering matrix to screen
  struct CLink *Columns;
  struct CLink *Rows;

  printf("\n    ");
    Columns=CM->ColLink;
    while ( Columns!=0)
    {
      printf ("%d ",Columns->Cost);
      Columns=Columns->Next;
    }
  printf("\n");
  Rows=CM->RowLink;
  while ( Rows!=0)
   {
    printf ( "%2d- ",Rows->ID);
    Columns=CM->ColLink;
    while ( Columns!=0)
    {
      printf ("%d ",*(CM->Mat+Rows->Offset+Columns->Offset));
      Columns=Columns->Next;
    }
    printf ("\n");
    Rows=Rows->Next;
   }
}

void AddDomain ( struct Cube *SolCube, struct SetCols *Domain ) {
	
	struct SetCols *Set;
	struct SetCols *Aux;
	
	Set = Domain;

	if (SolCube->SetC == 0){

		if (Set != 0 ){
			SolCube->SetC = new SetCols;
			SolCube->SetC->Next = NULL;
			SolCube->SetC->ColumnNumber = Set->ColumnNumber;
			SolCube->SetC->ColumnCost = Set->ColumnCost;
			Aux = SolCube->SetC;
			Set = Set->Next;
		}

		while ( Set != 0) {
			Aux->Next = new SetCols;
			Aux = Aux->Next;
			Aux->ColumnNumber = Set->ColumnNumber;
			Aux->ColumnCost = Set->ColumnCost;
			Aux->Next = NULL;
			Set =  Set->Next;		 
			}		
		
	}else { 

		while ( SolCube->Next != 0 )  SolCube = SolCube->Next;
		SolCube->Next = new Cube;
		SolCube->Next->Next = 0;
		SolCube->Next->Previous = SolCube;
		SolCube->Next->SetC = 0;
		SolCube = SolCube->Next;

		if (Set != 0 ){
			SolCube->SetC = new SetCols;
			SolCube->SetC->Next = NULL;
			SolCube->SetC->ColumnNumber = Set->ColumnNumber;
			SolCube->SetC->ColumnCost = Set->ColumnCost;
			Aux = SolCube->SetC;
			Set = Set->Next;
		}

		while ( Set != 0) {
			Aux->Next = new SetCols;
			Aux = Aux->Next;
			Aux->ColumnNumber = Set->ColumnNumber;
			Aux->ColumnCost = Set->ColumnCost;
			Aux->Next = NULL;
			Set =  Set->Next;		 
			}		
		
	}	
}

void AddColumntoSet ( struct SetCols *SetC, struct CLink *Column ) {

	struct SetCols *Solution;
	struct SetCols *Aux;
	struct SetCols *Columns;

//	Aux = new SetCols;
//	Aux = SetC;


	Solution = new SetCols;
	if ( Solution == NULL ) {
		printf ("Insufficient memory \n");
	  	exit(0);
      }

	Solution->ColumnNumber = Column->ID;
	Solution->ColumnCost = Column->Cost;
	Solution->Next = 0;

//	if ( SetC->ColumnNumber == 0) {
	if ( SetC->ColumnCost == 0) {
		SetC->ColumnNumber = Column->ID;
	    SetC->ColumnCost = Column->Cost;
	    SetC->Next = 0;
		Release (Solution);
	//	SetC = Solution;
	//	printf("prirazuji PRVNE Solution do SetC");

	}
	else {
		Aux = SetC;
		while ( Aux->Next != 0 ) Aux = Aux->Next;
		Aux->Next = Solution;
	}

}


void printSet (struct SetCols *SetC ){

	struct SetCols *Aux;
	Aux = SetC;
	while (Aux!=0){
		printf ("Je tam sloupce cislo %d", Aux->ColumnNumber);
		Aux = Aux->Next;
	}

}

void CreateCube ( struct CoveringMatrix *CM, struct HeaderSetRows *SetMSIR, struct Cube *SolCube ) {


	struct Cube *Aux;
	struct SetCols *SolPart;
	struct CLink *ColLink;
	struct SetRows *Rows;
	unsigned char *RowOffset;

	Rows = SetMSIR->RowsLink;
	
	
//	printf("pocatek createCUBE");

	while ( Rows != 0  ) {

		SolPart = InitCols();
		RowOffset = CM->Mat + Rows->Offset;
			

//		Print(CM);
		ColLink = CM->ColLink;

		while ( ColLink != 0 ) {
			if ( *(RowOffset + ColLink->Offset ) == 1 ) AddColumntoSet ( SolPart, ColLink );
			ColLink = ColLink -> Next;
		}
		AddDomain (SolCube, SolPart);

//		printSet (SolCube->SetC);

		Rows = Rows->Next;
		Release (SolPart);

//		printf("konec createCUBE");
	}

}

struct Cube *CopyCube ( struct Cube *SolCube ) {

	struct Cube *Copy;
	struct SetCols *CubeSetC;
	struct SetCols *Columns;
	


	CubeSetC = SolCube->SetC;
	Copy = new Cube;
	if ( Copy == NULL ) {
	printf ("Insufficient memory \n");
	exit(0);
      }

//	Copy->SetC = new SetCols;
	Copy->SetC = 0;
	Copy->Next = NULL;
	Copy->Previous = NULL;

	while ( SolCube != 0){

		AddDomain (Copy, SolCube->SetC);
		SolCube = SolCube->Next;

	}
	return Copy;

}


void AppendSolution (struct HeaderSol *Source,struct HeaderSol *Target )
{//function to apend partial solution to solution of UCP
  struct SetCols *Aux;

  //if there are no cols in solution of UCP
  if ( Target->SetC==0 ) Target->SetC=Source->SetC;
   else
     { //else connect to the end of link
       Aux=Target->SetC;
       while ( Aux->Next!=0 )
	 Aux=Aux->Next;
       Aux->Next=Source->SetC;
     }
  Target->Cost+=Source->Cost;
  delete (Source);//delete header of partial solution,it is no inter needed
}

void AddToSolution ( struct HeaderSol *SolutionUCP,struct CLink *Column )
{//Function to add column number to solution
     struct SetCols *Solution;
     struct SetCols *Aux;

     Solution=new SetCols;
     if ( Solution==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
     Solution->ColumnNumber=Column->ID;
     Solution->ColumnCost=Column->Cost;      // kvuli rychlemu nalezeni ceny sloupce v SolCube
     Solution->Next=0;

     if ( SolutionUCP->SetC==0 )
	{//if there are no entries in solution
	  SolutionUCP->SetC=Solution;
	  SolutionUCP->Cost=Column->Cost;
	}
      else
       {//else append it to the end od links
	 SolutionUCP->Cost+=Column->Cost;
	 Aux=SolutionUCP->SetC;
	 while ( Aux->Next!=0 )
	 Aux=Aux->Next;
	 Aux->Next=Solution;
       }
}

void AddToSetRows ( struct HeaderSetRows *HSR,int Offset )
{//Function to add row entry to set
     struct SetRows *RowToAdd;
     struct SetRows *Aux;

     RowToAdd=new SetRows;
     if ( RowToAdd==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
     RowToAdd->Offset=Offset;
     RowToAdd->Next=0;
     //if set is empty
     if ( HSR->RowsLink==0 )
	{
	  HSR->RowsLink=RowToAdd;
	}
      else
       {//else append to the end
	 Aux=HSR->RowsLink;
	 while ( Aux->Next!=0 )
	 Aux=Aux->Next;

	 Aux->Next=RowToAdd;
       }
}

void PrintSolution ( struct HeaderSol *SolutionUCP )
{
   struct SetCols *Aux;
//   int Cost=0;
   Aux=SolutionUCP->SetC;
   while (Aux!=0 )
     {
	fprintf(NAME,"%d ",Aux->ColumnNumber );
	printf("%d ",Aux->ColumnNumber );
//	Cost++;
	Aux=Aux->Next;
     }

  fprintf(NAME,"\nCost: %lu\n\n----------------------------\n",SolutionUCP->Cost);
  printf("\nCost: %lu\n\n----------------------------\n",SolutionUCP->Cost);
}

void RemoveColumn ( struct CoveringMatrix *CM, struct CLink *Entry )
{//remove column from covering matrix
  struct CLink *Aux;
  if ( CM->ColLink !=0 )
    {
	if ( Entry->Next != 0&&Entry->Previous!=0 )
	  {
	   Entry->Next->Previous=Entry->Previous;
	   Entry->Previous->Next=Entry->Next;
	  }
       else
	if ( Entry->Next!=0&&Entry->Previous==0	)
	  {
	   Entry->Next->Previous=0;
	   CM->ColLink=Entry->Next;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous!=0 )
	  {
	   Entry->Previous->Next=0;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous==0 )
	  {//if it is the only column in the matrix,all rows must be deleted
	   //to set the matrix empty
	   CM->ColLink=0;
	   while (CM->RowLink!=0)
	    {//release allocated memory for rows
	      Aux=CM->RowLink->Next;
	      delete (CM->RowLink);
	      CM->RowLink=0;
	      CM->RowLink=Aux;
	   }
	   CM->RowLink=0;

	  }
	CM->M--;//decrease dimension of matrix
	delete (Entry);//delete column
    }
}

void RemoveRow ( struct CoveringMatrix *CM, struct CLink *Entry )
{
  struct CLink *Aux;

  if ( CM->RowLink !=0 )
    {

	if ( Entry->Next != 0 &&Entry->Previous!=0 )
	  {
	   Entry->Next->Previous=Entry->Previous;
	   Entry->Previous->Next=Entry->Next;
	  }
       else
	if ( Entry->Next!=0 &&Entry->Previous==0	)
	  {
	   Entry->Next->Previous=0;
	   CM->RowLink=Entry->Next;
	  }
	else
	if ( Entry->Next == 0 &&Entry->Previous!=0 )
	  {
	   Entry->Previous->Next=0;
	  }
	else
	if ( Entry->Next == 0&&Entry->Previous==0 )
	  {
	   CM->RowLink=0;
	   while (CM->ColLink!=0)
	    {//if it is the only row in the matrix,all columns must be deleted
	   //to set the matrix empty
	      Aux=CM->ColLink->Next;
	      delete (CM->ColLink);
	      CM->ColLink=0;
	      CM->ColLink=Aux;
	   }
	   CM->ColLink=0;
	  }
	 delete (Entry);//delete row
	 CM->N--;//decrease dimension of matrix
    }
}

void RemoveColWithRows ( struct CLink * Column, struct CoveringMatrix *CM )
{//Function to remove column and all rows it covers
  struct CLink *RowLink;
  struct CLink *Aux;

  RowLink = CM->RowLink;
  while ( RowLink!=0)
   {
    if ( *(CM->Mat+RowLink->Offset+Column->Offset)==1 )
       {//if column intersect row,it will be deleted
	  Aux=RowLink->Next;
	  RemoveRow(CM,RowLink );
       }
     else Aux=RowLink->Next;
      RowLink=Aux;
   }//by deleting all rows int the matrix,all cols should be deleted too
   //if there is a column in the matrix,delete current column
   if ( CM->ColLink!=0 ) RemoveColumn ( CM,Column );
}

void RemoveColWithRowsClearContr ( struct CLink * Column, struct CoveringMatrix *CM )
{//Function to remove column and all rows it covers
  struct CLink *RowLink;
  struct CLink *Aux;
  struct CLink *ColAux;


  RowLink = CM->RowLink;
  while ( RowLink!=0)
   {
    if ( *(CM->Mat+RowLink->Offset+Column->Offset)==1 )
       {//if column intersect row,it will be deleted
	  ColAux = CM->ColLink;
	  while ( ColAux !=NULL )
	    {
	       if ( *(CM->Mat+RowLink->Offset+ColAux->Offset)==1 )
		 {
		    ColAux->NumberOf1=0;
		 }
	       ColAux=ColAux->Next;
	    }
	  Aux=RowLink->Next;
	  RemoveRow(CM,RowLink );
       }
     else Aux=RowLink->Next;
      RowLink=Aux;
   }//by deleting all rows int the matrix,all cols should be deleted too
   //if there is a column in the matrix,delete current column
   if ( CM->ColLink!=0 ) RemoveColumn ( CM,Column );
}


void RemoveMSIRRows ( struct CoveringMatrix *CML, struct HeaderSetRows *SetMSIR ) {

	struct CLink *CMLRowLink;
	struct SetRows *MSIRRowLink;

	CMLRowLink = CML->RowLink;
	

	while ( CMLRowLink != 0 ) {
		
		MSIRRowLink = SetMSIR->RowsLink;
		while ( MSIRRowLink != 0 ) {
			
			if ( CMLRowLink->Offset == MSIRRowLink->Offset ) RemoveRow ( CML, CMLRowLink); 
			MSIRRowLink =  MSIRRowLink->Next;
		}
		CMLRowLink = CMLRowLink->Next;
	}

}




struct CoveringMatrix *Duplicate ( struct CoveringMatrix *CM)
{//Function to duplicate links to rows and cols of covering matrix
  struct CoveringMatrix *Copy;
  struct CLink *Rows;
  struct CLink *Columns;
  struct CLink *CMRowLink;
  struct CLink *CMColLink;

  CMRowLink=CM->RowLink;
  CMColLink=CM->ColLink;
  Copy=new CoveringMatrix;
  if ( Copy==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
//  Copy->NumCalls=NumCalls;
  Copy->Cost=CM->Cost;
  Copy->M=CM->M;
  Copy->N=CM->N;
  Copy->Mat=CM->Mat;//Sel all antries of created link to
  //values of link of original matrix
  Copy->ColLink=NULL;
  Copy->RowLink=NULL;

  if ( CM->RowLink!=NULL )
    {//if there are another entries,add it to duplicated matrix
      Copy->RowLink=new CLink;
      if ( Copy->RowLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }
      Copy->RowLink->Previous=NULL;
      Copy->RowLink->Next=NULL;
      Copy->RowLink->Offset=CM->RowLink->Offset;
      Copy->RowLink->ID=CM->RowLink->ID;
      Copy->RowLink->NumberOf1=CM->RowLink->NumberOf1;
      Copy->RowLink->Cost=CM->RowLink->Cost;
      Rows=Copy->RowLink;
      CMRowLink=CM->RowLink->Next;


  while ( CMRowLink!=NULL )
   {
     Rows->Next=new CLink;
     if ( Rows->Next==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Rows->Next->Previous=Rows;
     Rows=Rows->Next;
     Rows->Offset=CMRowLink->Offset;
     Rows->ID=CMRowLink->ID;
     Rows->NumberOf1=CMRowLink->NumberOf1;
     Rows->Cost=CMRowLink->Cost;
//Sel all antries of created link to
  //values of link of original matrix
     Rows->Next=NULL;
     CMRowLink=CMRowLink->Next;
   }
  }

  if ( CM->ColLink!=NULL )
     {

       Copy->ColLink = new CLink;
       if ( Copy->ColLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

       Copy->ColLink->Previous=NULL;
       Copy->ColLink->Next=NULL;
       Copy->ColLink->Offset=CM->ColLink->Offset;
       Copy->ColLink->NumberOf1=CM->ColLink->NumberOf1;
       Copy->ColLink->Cost=CM->ColLink->Cost;
       Copy->ColLink->ID=CM->ColLink->ID;
       Columns=Copy->ColLink;
       CMColLink=CM->ColLink->Next;
//Sel all antries of created link to
  //values of link of original matrix

 while ( CMColLink!=NULL )
   {
     Columns->Next=new CLink;
     if ( Columns->Next==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

      Columns->Next->Previous=Columns;
     Columns=Columns->Next;

     Columns->Offset=CMColLink->Offset;
     Columns->ID=CMColLink->ID;
     Columns->NumberOf1=CMColLink->NumberOf1;
     Columns->Cost=CMColLink->Cost;

     Columns->Next=NULL;
     CMColLink=CMColLink->Next;
//Sel all antries of created link to
  //values of link of original matrix
    }
   }
  return Copy;
}





void CreateLinks ( struct CoveringMatrix *Cm )
{//Function to create row and column links of covering matrix
  unsigned int I,J;
  struct CLink *Columns;
  struct CLink *Rows;
  //Create row links
  Cm->RowLink = new CLink;
  if ( Cm->RowLink==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

  Cm->RowLink->Previous=0;
  Cm->RowLink->Offset=Cm->M;
  Cm->RowLink->ID=1;
  Cm->RowLink->NumberOf1=0;
  Rows=Cm->RowLink;
  for ( I=2;I<=Cm->N;I++)
   {
     Rows->Next=new CLink;
     if ( Rows->Next==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Rows->Next->Previous=Rows;
     Rows=Rows->Next;
     Rows->Offset=I*Cm->M*sizeof(char);
     Rows->ID=I;
     Rows->NumberOf1=0;
     Rows->Next=0;
   }
  //Create column links
  Cm->ColLink = new CLink;
  if ( Cm->ColLink==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

  Cm->ColLink->Previous=0;
  Cm->ColLink->Offset=0;
  Cm->ColLink->NumberOf1=0;
  Cm->ColLink->ID=1;
  Cm->ColLink->Cost=*(Cm->Mat);//cost of the column is kept at the beginning
				//of array
  uBound+=Cm->ColLink->Cost;//upper bound is computed here
  Columns=Cm->ColLink;

  for ( I=1;I<Cm->M;I++)
   {
     Columns->Next=new CLink;

     if ( Columns->Next==NULL)
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

     Columns->Next->Previous=Columns;
     Columns=Columns->Next;
     Columns->Offset=I*sizeof(char);
     Columns->ID=I+1;
     Columns->NumberOf1=0;
     Columns->Cost=*(Cm->Mat+I);//cost of column
     uBound+=Columns->Cost;//increase upper bound
     Columns->Next=0;
   }
   uBound++;   //????????
   MaxCost=uBound;
}
struct CoveringMatrix *Load ( char *Filename )
{
  FILE *Name;
  unsigned int I,J;
  unsigned char Character;
  unsigned int Size;
  struct CoveringMatrix *Cm;

   Cm=new CoveringMatrix;
   if ( Cm==NULL )
       {
	  printf ("Insufficient memory \n");
	  exit(0);
       }

   Cm->Cost=0;
   Cm->M=0;
   Cm->N=0;
   Cm->Mat=NULL;

  if ( (Name=fopen(Filename, "rt"))==NULL)

     {
       printf ("Error opening file %s\n",Filename);
      exit(0);
     }
  Character=fgetc(Name);
  //first load dimensions of array to allocate memory
  while (Character>=48 && Character <= 57 )
    {
       Cm->M=Cm->M*10+Character-48;
       Character=fgetc(Name);
    }

  Character=fgetc(Name);
  while (Character>=48 && Character <= 57 )
    {
       Cm->N=Cm->N*10+Character-48;
       Character=fgetc(Name);
    }
 
  //compute the size to allocate,N+1 since costs of columns will be stored
  //at the beginning of array
   Size=(Cm->M*(Cm->N+1))*sizeof(char);
  Cm->Mat=new unsigned char [Size];
  if ( Cm->Mat==0 )

    {
	printf("Insufficient memory");
	exit(0);

    }

 //Load array

 for ( J=0;J<=Cm->N;J++)
  {
  for ( I=0;I<Cm->M;I++ )
   {
      *(Cm->Mat+I+J*Cm->M)=fgetc(Name)-48;
     Character=fgetc(Name);
	
     while (Character!=' ')
       {
	 *(Cm->Mat+I+J*Cm->M)*=10;
	 *(Cm->Mat+I+J*Cm->M)+=Character-48;
         fgetc(Name);
       }//space
	 

   }
  fgetc(Name); //Enter
  }
  printf ("nacteno");
  fclose(Name);
  CreateLinks ( Cm);
  return Cm;

}

void R_Dominance ( struct CoveringMatrix *CM,struct HeaderSol *SolutionUCP )
{//reduce the matrix by row dominance
  int Dominance;
  struct CLink *RowLink;
  struct CLink *Aux;
  struct CLink *ColLink;
  struct CLink *EssentialColumn;
  struct CLink *ComparedRow;
  int Dirty=0;
  unsigned int NumberOf1;
  unsigned char *ComparedRowOffset;
  unsigned char *OtherRowsOffset;

  ComparedRow=CM->RowLink;


  while ( ComparedRow != 0 )  //Row to compare
   {
      ComparedRowOffset=CM->Mat+ComparedRow->Offset;
      RowLink=CM->RowLink;  //
		//Other rows are compared,looking for dominance
      while ( RowLink!=0 )
	{
	  Dominance=0;
	  OtherRowsOffset=CM->Mat+RowLink->Offset;
	  ColLink=CM->ColLink;
	  NumberOf1=0;
	  EssentialColumn=NULL;
	  while ( ColLink!=0 )
	   {

	     if ( *(ComparedRowOffset+ColLink->Offset)==1 )
	      {
	      if ( *(OtherRowsOffset+ColLink->Offset)==1 )
	      {   //if ComparedRow has ones at the same position as the second,domitates
		if ( Dominance!=-1 ) Dominance=1;
	      }
	      else  { Dominance=-1; }//dominance failed
	      EssentialColumn=ColLink;
	      NumberOf1++;
	     }
	    ColLink=ColLink->Next;
	   }
	  if (Dominance==1&&RowLink->ID!=ComparedRow->ID)
	    {//if copare row with itself,it cannot be removed
		Aux=RowLink->Next;
		RemoveRow (CM,RowLink );
		Dirty = 1;
	    }
	  else Aux=RowLink->Next;
	 RowLink=Aux;

      }
     if ( NumberOf1==1)
     {//if row is covered by only one column,it is esential column,
      //will be added to solution and removed from matrix with
      //rows it covers
	AddToSolution ( SolutionUCP,EssentialColumn);
	Aux=ComparedRow->Next;
	RemoveColWithRows(EssentialColumn,CM);
	Dirty = 1;
	ComparedRow=Aux;
     }
   else ComparedRow=ComparedRow->Next;
  }
CM->Dirty=Dirty;
}

void S_Dominance ( struct CoveringMatrix *CM)
{//reduce the matrix by column dominance
  int Dominance;
  int Dirty=0;
  struct CLink *RowLink;
  struct CLink *Aux;
  struct CLink *ColLink;
  struct CLink *ComparedCol;
  unsigned char *ComparedColOffset;
  unsigned char *OtherColOffset;

  ComparedCol=CM->ColLink;

  while ( ComparedCol != 0 )  //Column to compare
   {
      ComparedColOffset=CM->Mat+ComparedCol->Offset;

      ColLink=CM->ColLink;
      while ( ColLink!=0 )
	{
	  Aux=ColLink->Next;
	  OtherColOffset=CM->Mat+ColLink->Offset;
	  if ( ColLink->ID!=ComparedCol->ID )
	  {//To disable compare column with itself
	  Dominance=0;
	  RowLink=CM->RowLink;
	  while ( RowLink!=0 )
	   {
	    if ( *(OtherColOffset+RowLink->Offset)==1 )
	      if ( *(ComparedColOffset+RowLink->Offset)==1 )
	      {   //if ComparedCol has ones at the same position as second col
		  //it has less ones than second column,will be removed
		Dominance=1;
	      }
	      else  { Dominance=0; break; }//dominance failed
	    RowLink=RowLink->Next;
	   }
	  if (Dominance==1)  //column will be renoved here
	    {
		if ( ColLink->Cost >= ComparedCol->Cost ) //remove/add comment to keep
							  //column with less cost than copared col
							  //in matrix
		  {
		    RemoveColumn (CM,ColLink );
		    Dirty = 1;
		  }
	    }
	  }
	 ColLink=Aux;
	}

   ComparedCol=ComparedCol->Next;
  }
   CM->Dirty=Dirty;

//  return CM;
}

void FindNumberOf1 ( struct CoveringMatrix *CM )
{//function to find number of ones in rows and columns
 int One;
 struct CLink *Columns;
 struct CLink *Rows;

 Columns=CM->ColLink;
 while ( Columns!=0)
  {
    Columns->NumberOf1=0;
    Columns=Columns->Next;
  }
  Rows=CM->RowLink;
  while ( Rows!=0)
   {
     Rows->NumberOf1=0;
     Rows=Rows->Next;
   }
 Columns=CM->ColLink;
 while ( Columns!=0)
  {
    One=0;
    Rows=CM->RowLink;
  while ( Rows!=0)
   {
    One = *(CM->Mat+Columns->Offset+Rows->Offset);
    if (One )
     {
       Rows->NumberOf1+=One;
       Columns->NumberOf1+=One;
     }
    Rows=Rows->Next;
   }
  Columns=Columns->Next;
  }
}

/*
void FindLowest (struct CoveringMatrix *CM){

	struct CLink *Columns;
	

	Columns = CM->ColLink;
	LowestCost = Columns->Cost;
	while (Columns != 0){
		if (Columns->Cost < LowestCost) LowestCost = Columns->Cost;
		Columns = Columns->Next;
	}
}*/

void RecomputeNumberOf1 ( struct CoveringMatrix *CM )
{//function to find number of ones in rows and columns
 int One;
 struct CLink *Columns;
 struct CLink *Rows;

 Columns=CM->ColLink;
 while ( Columns!=0)
  {
  if ( Columns->NumberOf1 ==0 )
   {
   One=0;
   Rows=CM->RowLink;
   while ( Rows!=0)
    {
     One = *(CM->Mat+Columns->Offset+Rows->Offset);
     if (One )
      {
	Columns->NumberOf1+=One;
      }
     Rows=Rows->Next;
    }
    }
   Columns=Columns->Next;

  }
}


void SolveDominance ( struct CoveringMatrix *CM,struct HeaderSol *SolutionUCP )
{ //Reduce matrix with dominance relations
int ColDom=0;
 if ( CM->ColLink !=0 )
  {

   CM->Dirty=1;
//Dominance will be solved as long as any change has been made
   while (CM->Dirty)
    {
      R_Dominance(CM,SolutionUCP);
	if ( CM->Dirty==1||ColDom==0 )
	 {
	  CM->Dirty=0;
	  S_Dominance(CM);
	  ColDom=1;
	 }
    }
 }
}


int FindEssential ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

//Print (CM);

 struct CLink *ColLink;
 struct CLink *RowLink;
 struct CLink *EssentialColumn;
 struct CLink *Aux;
 unsigned char *RowOffset;

EssentialColumn = new CLink;
Aux = new CLink;

 int ColID;
 int essential; 	// essential = 0 - pocatecni nastaveni
			            // essential = 1 - radek obsahuje jedino jednicku
			            // essential = 2 - radek obsahuje vice jednicek 

 RowLink = CM->RowLink;
 

 while ( RowLink!=0 ) {
	RowOffset = CM->Mat+RowLink->Offset;
	ColLink = CM->ColLink;
	essential = 0;
	ColID = 0;

	while ( ColLink!=0 ) {
	  if ( *(RowOffset+ColLink->Offset)==1  ) {  // jestlize radek obsahuje jen jednu 1, essential se nastavi na hodnotu 1
		if ( essential == 0 ) {

//			printf("sloupec cislo %d. esen ",ColLink->ID);
			essential = 1;
			EssentialColumn = ColLink;
			ColID = ColLink->ID;
		}
		else if ((essential == 1 || essential == 2) && (ColID != ColLink->ID)){

//			printf("sloupec cislo %d. NONesen",ColLink->ID);
			essential = 2;
			EssentialColumn = 0;
		}		
	  }
	  ColLink=ColLink->Next;
   	}
	
	if ( essential == 1) {
//		printf("pridavam do reseni sloupec CISLO %d ",EssentialColumn->ID);
		AddToSolution ( SolUCP,EssentialColumn);
	    RemoveColWithRows( EssentialColumn, CM);
		FindEssential ( CM, SolUCP ); 
		return 0;
	}else RowLink = RowLink->Next;
 }
//printf("konec essential");
 return 0;
}


unsigned int ServitHeuristic ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;
float one = 1;

unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 float fractionalvalue=0; // pomocna promenna pro vypocet hodnoty sloupce ( uchovava se v ni castecna cena sloupce, 
				     // ktera musi byt invertovana, nez bude vynasobena se zbytkem )


ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			Aux = CM->ColLink;
			while ( Aux != 0 ) {                  //... projdeme vsechny sloupce radku v nemz ta jednicka byla

				if ( *(RowOffset + Aux->Offset)==1 ) { 
					fractionalvalue = fractionalvalue + ( one/(float)Aux->Cost );
	//				printf ("Fraction hodnota je je %f  ", fractionalvalue);
				}
				Aux = Aux->Next;
			}
			columnvalue += ( 1 / (float) columncost ) * ( 1 / fractionalvalue ); // spoctena hodnota sloupce
			fractionalvalue = 0;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota je %f  ", columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 
	if ( columnvalue == worstvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 RemoveColumn ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}



unsigned int RothHeuristic ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue = ( 1 / (float) columncost ) ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 

	if ( columnvalue == worstvalue ) { 
	random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//	   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 RemoveColumn ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}


unsigned int MichalskiHeuristic ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue++ ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 
	if ( columnvalue == worstvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}
	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 RemoveColumn ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}

unsigned int NeculaHeuristic ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue += 1/ColLink->Cost ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 
	if ( columnvalue == worstvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}
	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 RemoveColumn ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}

unsigned int BowmanHeuristic ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *WorstColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;
float one = 1;

unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float worstvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 float fractionalvalue=0; // pomocna promenna pro vypocet hodnoty sloupce ( uchovava se v ni castecna cena sloupce, 
				     // ktera musi byt invertovana, nez bude vynasobena se zbytkem )


ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

WorstColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 worstvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			Aux = CM->ColLink;
			while ( Aux != 0 ) {                  //... projdeme vsechny sloupce radku v nemz ta jednicka byla

				if ( *(RowOffset + Aux->Offset)==1 ) { 
					fractionalvalue++;
	//				printf ("Fraction hodnota je je %f  ", fractionalvalue);
				}
				Aux = Aux->Next;
			}
			columnvalue +=  ( 1 / fractionalvalue ); // spoctena hodnota sloupce
			fractionalvalue = 0;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota je %f  ", columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue < worstvalue || worstvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		WorstColumn = ColLink;
		worstvalue = columnvalue;
	} 
	if ( columnvalue == worstvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			WorstColumn = ColLink;
//			worstvalue = columnvalue;
		}
	}
	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
 RemoveColumn ( CM, WorstColumn );   //... odebereme ho tedy, protoze vsechny radky ktere pokryva, obsahuji 
                                     //minimalne jeste jednu jednicku a lze je tak pokryt 'lepsim' sloupcem
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}

//---------pozitivni heuristiky-----------------
//----------------------------------------------
//----------------------------------------------

unsigned int ServitHeuristicPositiv ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejlepsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;
float one = 1;

unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejlepsi hodnota sloupce k ( cena sloupce pro odebrani a pridani do reseni; odebira se sloupce s nejvyssi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 float fractionalvalue=0; // pomocna promenna pro vypocet hodnoty sloupce ( uchovava se v ni castecna cena sloupce, 
				     // ktera musi byt invertovana, nez bude vynasobena se zbytkem )


ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			Aux = CM->ColLink;
			while ( Aux != 0 ) {                  //... projdeme vsechny sloupce radku v nemz ta jednicka byla

				if ( *(RowOffset + Aux->Offset)==1 ) { 
					fractionalvalue = fractionalvalue + ( one/(float)Aux->Cost );
	//				printf ("Fraction hodnota je je %f  ", fractionalvalue);
				}
				Aux = Aux->Next;
			}
			columnvalue += ( 1 / (float) columncost ) * ( 1 / fractionalvalue ); // spoctena hodnota sloupce
			fractionalvalue = 0;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota je %f  ", columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s lepsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 
	if ( columnvalue == bestvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejlepsi (nejvyssi) hodnotou mame ulozen v promene BestColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

      

return 0;
}



unsigned int RothHeuristicPositiv ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue = ( 1 / (float) columncost ) ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s horsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 

	if ( columnvalue == bestvalue ) { 
	random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//	   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejhorsi (nejnizsi) hodnotou mame ulozen v promene WorstColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice

 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}


unsigned int MichalskiHeuristicPositiv ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue++ ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s lepsi hodnotou nez dosud nalezenou

		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 
	if ( columnvalue == bestvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejlepsi (nejvyssi) hodnotou mame ulozen v promene BestColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky    

return 0;
}



unsigned int NeculaHeuristicPositiv ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;


unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 

ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			
			columnvalue += 1/ColLink->Cost ; // spoctena hodnota sloupce
			break;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota sloupce %d je %f  ",ColLink->ID, columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s lepsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 
	if ( columnvalue == bestvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejlepsi (nejvyssi) hodnotou mame ulozen v promene BestColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}


unsigned int BowmanHeuristicPositiv ( struct CoveringMatrix *CM, struct HeaderSol *SolUCP ) {

struct CLink *ColLink;
struct CLink *RowLink;
struct CLink *Aux;          // pomocna promena pro vnitrni cyklus prochazeni sloupcu
struct CLink *BestColumn;   // sloupec s nejhorsi cenou, jenz bude odebran
unsigned char *RowOffset;
int val ;
float one = 1;

unsigned int columncost;  // cena sloupce, pro nejz pocitame prave hodnotu
 float bestvalue ;  // nejhorsi hodnota sloupce k ( cena sloupce pro odebrani; odebira se sloupce s nejnizsi hodnotou )
 float columnvalue; // hodnota prave pocitaneho sloupce
 float fractionalvalue=0; // pomocna promenna pro vypocet hodnoty sloupce ( uchovava se v ni castecna cena sloupce, 
				     // ktera musi byt invertovana, nez bude vynasobena se zbytkem )


ColLink = new CLink;
RowLink = new CLink;
Aux = new CLink;

BestColumn = new CLink;

while ( true ) {    // hlavni cyklus heuristiky

 val = FindEssential ( CM, SolUCP );    // najdi esencialni sloupce a pridej je do reseni

 RowLink = CM->RowLink;
 ColLink = CM->ColLink;
 bestvalue = -1;

 if ( RowLink == 0 ) break;       // jestlize uz v matici neni zadny radek k pokryti, ukonci cyklus (nasli jsme reseni)
 if ( ColLink == 0 && RowLink != 0 ) {  // jestlize jsou v matici radky, ktere nejsou pokryty zadnym sloupcem, matice nema reseni
	SolUCP = 0;
	break;
 }


 while ( ColLink != 0 ) { // prochazi vsechny sloupce matice a pocitame pro ne hodnotu. Sloupec s nejhorsi (nejnizsi)
				  // hodnotou bude ulozen do WorstColumn		
	columncost = ColLink->Cost;   // cena sloupce pro nejz prave pocitame hodnotu
	columnvalue = 0; //  vynulovani promene, abychom do ni mohli pocitat hodnotu dalsiho sloupce


	 RowLink = CM->RowLink;
	
	 
	while ( RowLink != 0 ) {

		RowOffset = CM->Mat + RowLink->Offset;
		if ( *(RowOffset + ColLink->Offset)==1 ) {  // pro kazdou jednicku ve sloupci na kterou narazime .... 
			Aux = CM->ColLink;
			while ( Aux != 0 ) {                  //... projdeme vsechny sloupce radku v nemz ta jednicka byla

				if ( *(RowOffset + Aux->Offset)==1 ) { 
					fractionalvalue++;
	//				printf ("Fraction hodnota je je %f  ", fractionalvalue);
				}
				Aux = Aux->Next;
			}
			columnvalue +=  ( 1 / fractionalvalue ); // spoctena hodnota sloupce
			fractionalvalue = 0;   // vynulovani pomocne promenne ( pro kazdy radek se musi pocitat znovu )
//			printf ("spoctena hodnota je %f  ", columnvalue);
		} 
		RowLink = RowLink->Next;

	} 
	if ( columnvalue > bestvalue || bestvalue == -1 ) {  // jestlize jsme nalezli sloupec s lepsi hodnotou nez dosud nalezenou
//      printf (" sloupec cislo %d je NEJHORSI. s hodnotou %f", ColLink->ID, columnvalue);
		BestColumn = ColLink;
		bestvalue = columnvalue;
	} 
	if ( columnvalue == bestvalue ) { 
		random2 = (((double) rand() / (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
		if ( random2-1 ) { 
			BestColumn = ColLink;
//			bestvalue = columnvalue;
		}
	}

	ColLink = ColLink->Next;  // jdeme pocitat hodnotu dalsiho sloupce
	
 }   // timto jsme prosli vsechny sloupce a sloupec s nejlepsi (nejvyssi) hodnotou mame ulozen v promene BestColumn...

// printf (" ODEBIRAM sloupec %d  s hodnotou %f", WorstColumn->ID, worstvalue);
  AddToSolution ( SolUCP,BestColumn );   //... pridame ho tedy do reseni 
  RemoveColWithRows ( BestColumn,CM );  // ... a odebereme ho z matice
 
 // ...a pokracujeme v hlavnim cyklu otestovanim, zda matice uz neni prazdna..

}  // konec hlavniho cyklu heuristiky

return 0;
}



void NaturalHeuristic ( struct CoveringMatrix *CM,struct HeaderSol *SolUCP,int Dominance=0 )
{ //This heuristic consist in choosing columns which covers the largest
  //number of rows
 struct CLink *ColLink;
 struct CLink *SelectedColumn;
 NumCalls++;
 while ( CM->ColLink !=0 )
  {
   if ( Dominance ) SolveDominance(CM,SolUCP);
    if ( CM->ColLink !=0 )
    {
    FindNumberOf1(CM);
    ColLink=CM->ColLink;
    SelectedColumn=CM->ColLink;
    while ( ColLink!=0 )
      {//find column with largest number of ones
	  if ( ColLink->NumberOf1==SelectedColumn->NumberOf1 )
	    {
 		if ( ColLink->Cost<SelectedColumn->Cost ) SelectedColumn=ColLink;
		 else if ( ColLink->Cost == SelectedColumn->Cost ) {
		   random2 = (((double) rand() / 
                       (double) RAND_MAX) * 2 + 1);
//		   printf(" nahodne je %d \n",random2-1);
	           if ( random2-1 ) SelectedColumn=ColLink;
		}
	    }
	  if ( ColLink->NumberOf1>SelectedColumn->NumberOf1 )
	  SelectedColumn=ColLink;
	  ColLink=ColLink->Next;
      }
    if ( SelectedColumn->NumberOf1 !=0 )
     {
      AddToSolution ( SolUCP,SelectedColumn );
     }
      RemoveColWithRows ( SelectedColumn,CM );
    }
   }


 }



void Choose ( struct CoveringMatrix *CM )
{//Evaluates columns according to number covered rows
  //with respect to "quality" of covering
 int One;
 struct CLink *ColLink;
 struct CLink *Rows;
 struct CLink *Sloupce2;

 ColLink=CM->ColLink;
 RecomputeNumberOf1(CM);
 while ( ColLink!=0)
  {
  ColLink->NumberOf1=0;
  One=0;
  Rows=CM->RowLink;
  while ( Rows!=0)
   {
    One = *(CM->Mat+ColLink->Offset+Rows->Offset);
    if (One ) {
       ColLink->NumberOf1+=CM->M-Rows->NumberOf1;
     }
    Rows=Rows->Next;
   }
  ColLink=ColLink->Next;
 }
}


void ContribAddHeuristic ( struct CoveringMatrix *CM,struct HeaderSol *SolUCP,int Dominance=0  )
{ //Select column with most ones in rows with few ones
 struct CLink *ColLink;
 struct CLink *SelectedColumn;
 NumCalls++;
 while ( CM->ColLink !=0 )
  {
    if ( Dominance ) SolveDominance (CM,SolUCP);
   if ( CM->ColLink !=0 )
    {

    Choose(CM);

    ColLink=CM->ColLink;
    SelectedColumn=CM->ColLink;
    while ( ColLink!=0 )
      {
	  if ( ColLink->NumberOf1==SelectedColumn->NumberOf1 )
	    {
 		if ( ColLink->Cost<SelectedColumn->Cost ) SelectedColumn=ColLink;
		else if ( ColLink->Cost == SelectedColumn->Cost ){
		   random2 = (((double) rand() / 
                       (double) RAND_MAX) * 2 + 1);
//			   printf(" nahodne je %d \n",random2-1);
	           if ( random2-1 ) SelectedColumn=ColLink;
		}
	    }
	  if ( ColLink->NumberOf1>SelectedColumn->NumberOf1 )
	  SelectedColumn=ColLink;
	  ColLink=ColLink->Next;
      }
     {
      AddToSolution ( SolUCP,SelectedColumn );
     }
      RemoveColWithRowsClearContr ( SelectedColumn,CM );
    }
   }

}






float GetMyCPUTime()
{
    HANDLE hProcess; // specifies the process of interest
    FILETIME lpCreationTime; // when the process was created
    FILETIME lpExitTime; // when the process exited
    FILETIME lpKernelTime; // time the process has spent in kernel mode
    FILETIME lpUserTime;
    LARGE_INTEGER t1, t2;


    hProcess = GetCurrentProcess();
    GetProcessTimes(hProcess, &lpCreationTime, &lpExitTime, &lpKernelTime, 
&lpUserTime);
    memcpy(&t1, &lpUserTime, sizeof(FILETIME));
    memcpy(&t2, &lpKernelTime, sizeof(FILETIME));
    return ((float)(t1.QuadPart+t2.QuadPart)/10000000);
}


float MatrixDensity ( struct CoveringMatrix *CM )
{
  float NumberOf1=0;
  struct CLink *Column;
  struct CLink *Row;
  Column=CM->ColLink;
  while ( Column !=NULL)
   {
     Row=CM->RowLink;
     while ( Row!=NULL )
       {
	  NumberOf1+=*(CM->Mat+Column->Offset+Row->Offset);
	  Row=Row->Next;
       }
     Column=Column->Next;
   }
 return 1/((CM->M*CM->N)/NumberOf1);
}
int main ( int argc, char* argv[] )
{
  // struct time StartTime,StopTime;
   struct CoveringMatrix *CM;
   struct CoveringMatrix *Cm;
   struct CoveringMatrix *CM1;
   struct CoveringMatrix *CM2;
   struct CoveringMatrix *CM3;
   struct CoveringMatrix *CM4;
   struct CoveringMatrix *CM5;
   struct CoveringMatrix *CM6;
   struct CoveringMatrix *CM7;
   struct CoveringMatrix *CM8;
   struct CoveringMatrix *CM9;
   struct CoveringMatrix *CM10;
   struct CoveringMatrix *CM11;
   struct CoveringMatrix *CM12;
   struct CoveringMatrix *CM13;
   struct CoveringMatrix *CM14;
   struct HeaderSol *SolutionUCP;
   int I,Dominance=0;
   char *OutputFile;
//	unsigned int Hmin,Hmax,Hprum;
 //  double Time;
   float timex = 0;
   float timex1;
   float timex2;
   float timex3;
   float timex4;
   float timex5;
   float timex6;
   float timex7;
   float timex8;
   float timex9;
   float timex10;
   float timex11;
   float timex12;
   float timex13;
   float timex14;

   int mincost1,maxcost1; float everagecost1;
   int mincost2,maxcost2; float everagecost2;
   int mincost3,maxcost3; float everagecost3;
   int mincost4,maxcost4; float everagecost4;
   int mincost5,maxcost5; float everagecost5;
   int mincost6,maxcost6; float everagecost6;
   int mincost7,maxcost7; float everagecost7;
   int mincost8,maxcost8; float everagecost8;
   int mincost9,maxcost9; float everagecost9;
   int mincost10,maxcost10; float everagecost10;
   int mincost11,maxcost11; float everagecost11;
   int mincost12,maxcost12; float everagecost12;

   int i;

   srand( (unsigned)time( NULL ) );
 
   if ( argc == 1 )
     {
	printf ("Usage: cover.exe input_file [output_file]\n");
	argv[1] = "C:\\prj\\bak\\cover\\debug\\matice.dat";
	//	exit(0);
     }

   Cm=Load (argv[1]);

   if ( argc == 3 ) OutputFile=argv[2];
      else OutputFile="Out.dat";
   if ( (NAME=fopen ( OutputFile,"at"))==NULL)
      {
	printf("Cannot open output file %s \n");
	exit(0);
      }

   CM1=Duplicate(Cm); // Roth Heuristic
   CM2=Duplicate(Cm); // BABLLB
   CM3=Duplicate(Cm); // AURA
   CM4=Duplicate(Cm); // Servit heuristic
   CM5=Duplicate(Cm); // Michalski heuristic
   CM6=Duplicate(Cm); // Necula heuristic
   CM7=Duplicate(Cm); // Bowman heuristic
   CM8=Duplicate(Cm); // Natural heuristic
   CM9=Duplicate(Cm); // Contrib Add heuristic
   CM10=Duplicate(Cm); // Positiv Servit heuristic
   CM11=Duplicate(Cm); // Positiv Bowman heuristic 
   CM12=Duplicate(Cm); // Positiv Necula heuristic
   CM13=Duplicate(Cm); // Positiv Michalski heuristic
   CM14=Duplicate(Cm); // Positiv Roth heuristic

   rand();

   fprintf(NAME," %dx%d \t  %f \t ",Cm->M,Cm->N,MatrixDensity(Cm));
   printf("Filename: %s,Dimensions %dx%d, density of matrix %f\n\n",argv[1],Cm->M,Cm->N,MatrixDensity(Cm));
   fclose (NAME);

  
   timex = GetMyCPUTime(); 

   
////////////////////////////////////////////
 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Natural heuristic\n");
 //fprintf (NAME, "Solving by Natural heuristic\n");

  for (i=0; i<10; i++){
   CM8=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   NaturalHeuristic ( CM8,SolutionUCP,0 );

   if ( i==0 ) { 
		mincost1 = SolutionUCP->Cost;
		maxcost1 = SolutionUCP->Cost;
		everagecost1 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost1 ) mincost1 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost1 ) maxcost1 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost1 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost1 = everagecost1/10;
   }
   Release (SolutionUCP);
   Release(CM8);

  }

  timex1 = GetMyCPUTime();
  printf("Natural heuristika trvala %f .",timex1-timex);
  fprintf(NAME, "%2.8f \t  ",timex1-timex);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f \n\n",mincost1,maxcost1,everagecost1);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost1,maxcost1,everagecost1);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


 //////////////////////////////////////////////////
 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Contrib Add heuristic\n");
 //fprintf (NAME, "Solving by Contrib Add heuristic\n");

  for (i=0; i<10; i++){
   CM9=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   ContribAddHeuristic ( CM9,SolutionUCP,0 );

   if ( i==0 ) { 
		mincost2 = SolutionUCP->Cost;
		maxcost2 = SolutionUCP->Cost;
		everagecost2 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost2 ) mincost2 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost2 ) maxcost2 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost2 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost2 = everagecost2/10;
   }
   Release (SolutionUCP);
   Release(CM9);

  }

  timex2 = GetMyCPUTime();
  printf("Contrib add heuristika trvala %f .",timex2-timex1);
  fprintf(NAME, "%2.8f   \t ",timex2-timex1);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost2,maxcost2,everagecost2);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost2,maxcost2,everagecost2);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


   ////////////////////////////////////////////


 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Roth heuristic\n");
 //fprintf (NAME, "Solving by Roth heuristic\n");

  for (i=0; i<10; i++){
   CM1=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   RothHeuristic ( CM1,SolutionUCP );

   if ( i==0 ) { 
		mincost3 = SolutionUCP->Cost;
		maxcost3 = SolutionUCP->Cost;
		everagecost3 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost3 ) mincost3 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost3 ) maxcost3 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost3 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost3 = everagecost3/10;
   }
   Release (SolutionUCP);
   Release(CM1);

  }

  timex3 = GetMyCPUTime();
  printf("Roth heuristika trvala %f .",timex3-timex2);
  fprintf(NAME, "%2.8f   \t ",timex3-timex2);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost3,maxcost3,everagecost3);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t  ",mincost3,maxcost3,everagecost3);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


 ////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Positiv Roth heuristic\n");
 //fprintf (NAME, "Solving by Positiv Roth heuristic\n");

  for (i=0; i<10; i++){
   CM14=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   RothHeuristicPositiv ( CM14,SolutionUCP );

   if ( i==0 ) { 
		mincost4 = SolutionUCP->Cost;
		maxcost4 = SolutionUCP->Cost;
		everagecost4 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost4 ) mincost4 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost4 ) maxcost4 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost4 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost4 = everagecost4/10;
   }
   Release (SolutionUCP);
   Release(CM14);

  }

  timex4 = GetMyCPUTime();
  printf("Positiv Roth heuristika trvala %f .",timex4-timex3);
  fprintf(NAME, "%2.8f   \t ",timex4-timex3);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost4,maxcost4,everagecost4);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost4,maxcost4,everagecost4);
  printf("---------------------------\n\n");
  //fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);

   ////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Michalski heuristic\n");
 //fprintf (NAME, "Solving by Michalski heuristic\n");

  for (i=0; i<10; i++){
   CM5=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   MichalskiHeuristic ( CM5,SolutionUCP );

   if ( i==0 ) { 
		mincost5 = SolutionUCP->Cost;
		maxcost5 = SolutionUCP->Cost;
		everagecost5 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost5 ) mincost5 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost5 ) maxcost5 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost5 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost5 = everagecost5/10;
   }
   Release (SolutionUCP);
   Release(CM5);

  }

  timex5 = GetMyCPUTime();
  printf("Michalski heuristika trvala %f .",timex5-timex4);
  fprintf(NAME, "%2.8f  \t  ",timex5-timex4);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost5,maxcost5,everagecost5);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost5,maxcost5,everagecost5);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


 ////////////////////////////////////////////

  NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Positiv Michalski heuristic\n");
 //fprintf (NAME, "Solving by Positiv Michalski heuristic\n");

  for (i=0; i<10; i++){
   CM13=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   MichalskiHeuristicPositiv ( CM13,SolutionUCP );

   if ( i==0 ) { 
		mincost6 = SolutionUCP->Cost;
		maxcost6 = SolutionUCP->Cost;
		everagecost6 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost6 ) mincost6 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost6 ) maxcost6 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost6 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost6 = everagecost6/10;
   }
   Release (SolutionUCP);
   Release(CM13);

  }

  timex6 = GetMyCPUTime();
  printf("Positiv Michalski heuristika trvala %f .",timex6-timex5);
  fprintf(NAME, "%2.8f   \t ",timex6-timex5);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost6,maxcost6,everagecost6);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost6,maxcost6,everagecost6);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);



   ////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Necula heuristic\n");
 //fprintf (NAME, "Solving by Necula heuristic\n");

  for (i=0; i<10; i++){
   CM6=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   NeculaHeuristic ( CM6,SolutionUCP );

   if ( i==0 ) { 
		mincost7 = SolutionUCP->Cost;
		maxcost7 = SolutionUCP->Cost;
		everagecost7 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost7 ) mincost7 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost7 ) maxcost7 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost7 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost7 = everagecost7/10;
   }
   Release (SolutionUCP);
   Release(CM6);

  }

  timex7 = GetMyCPUTime();
  printf("Necula heuristika trvala %f .",timex7-timex6);
  fprintf(NAME, "%2.8f   \t ",timex7-timex6);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost7,maxcost7,everagecost7);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost7,maxcost7,everagecost7);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


////////////////////////////////////////////

  NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Positiv Necula heuristic\n");
 //fprintf (NAME, "Solving by Positiv Necula heuristic\n");

  for (i=0; i<10; i++){
   CM12=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   NeculaHeuristicPositiv ( CM12,SolutionUCP );

   if ( i==0 ) { 
		mincost8 = SolutionUCP->Cost;
		maxcost8 = SolutionUCP->Cost;
		everagecost8 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost8 ) mincost8 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost8 ) maxcost8 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost8 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost8 = everagecost8/10;
   }
   Release (SolutionUCP);
   Release(CM12);

  }

  timex8 = GetMyCPUTime();
  printf("Positiv Necula heuristika trvala %f .",timex8-timex7);
  fprintf(NAME, "%2.8f    \t",timex8-timex7);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost8,maxcost8,everagecost8);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost8,maxcost8,everagecost8);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


   ////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Bowman heuristic\n");
 //fprintf (NAME, "Solving by Bowman heuristic\n");

  for (i=0; i<2; i++){
   CM7=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   BowmanHeuristic ( CM7,SolutionUCP );

   if ( i==0 ) { 
		mincost9 = SolutionUCP->Cost;
		maxcost9 = SolutionUCP->Cost;
		everagecost9 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost9 ) mincost9 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost9 ) maxcost9 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost9 += SolutionUCP->Cost;

   if ( i==1 ) {
		everagecost9 = everagecost9/2;
   }
   Release (SolutionUCP);
   Release(CM7);

  }

  timex9 = GetMyCPUTime();
  printf("Bowman heuristika trvala %f .",10*(timex9-timex8));
  fprintf(NAME, "%2.8f   \t ",10*(timex9-timex8));
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost9,maxcost9,everagecost9);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost9,maxcost9,everagecost9);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);



////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Positiv Bowman heuristic\n");
// fprintf (NAME, "Solving by Positiv Bowman heuristic\n");

  for (i=0; i<10; i++){
   CM11=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   BowmanHeuristicPositiv ( CM11,SolutionUCP );

   if ( i==0 ) { 
		mincost10 = SolutionUCP->Cost;
		maxcost10 = SolutionUCP->Cost;
		everagecost10 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost10 ) mincost10 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost10 ) maxcost10 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost10 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost10 = everagecost10/10;
   }
   Release (SolutionUCP);
   Release(CM11);

  }

  timex10 = GetMyCPUTime();
  printf("Positiv Bowman heuristika trvala %f .",timex10-timex9);
  fprintf(NAME, "%2.8f   \t ",timex10-timex9);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost10,maxcost10,everagecost10);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost10,maxcost10,everagecost10);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);



////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Servit heuristic\n");
// fprintf (NAME, "Solving by Servit heuristic\n");

  for (i=0; i<2; i++){
   CM4=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   ServitHeuristic ( CM4,SolutionUCP );

   if ( i==0 ) { 
		mincost11 = SolutionUCP->Cost;
		maxcost11 = SolutionUCP->Cost;
		everagecost11 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost11 ) mincost11 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost11 ) maxcost11 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost11 += SolutionUCP->Cost;

   if ( i==1 ) {
		everagecost11 = everagecost11/2;
   }
   Release (SolutionUCP);
   Release(CM4);

  }

  timex11 = GetMyCPUTime();
  printf("Servit heuristika trvala %f .",10*(timex11-timex10));
  fprintf(NAME, "%2.8f   \t ",10*(timex11-timex10));
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost11,maxcost11,everagecost11);
  fprintf(NAME, "%2.0d  \t %2.0d  \t %2.8f  \t ",mincost11,maxcost11,everagecost11);
  printf("---------------------------\n\n");
 // fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);



   ////////////////////////////////////////////

 NAME=fopen ( OutputFile,"at");
 printf ( "Solving by Positiv Servit heuristic\n");
// fprintf (NAME, "Solving by Positiv Servit heuristic\n");

  for (i=0; i<10; i++){
   CM10=Duplicate(Cm);
   SolutionUCP=Init();
   uBound=MaxCost;

   NumCalls=0;
   
   ServitHeuristicPositiv ( CM10,SolutionUCP );

   if ( i==0 ) { 
		mincost12 = SolutionUCP->Cost;
		maxcost12 = SolutionUCP->Cost;
		everagecost12 = SolutionUCP->Cost;
   }

   if ( SolutionUCP->Cost < mincost12 ) mincost12 = SolutionUCP->Cost;
   if ( SolutionUCP->Cost > maxcost12 ) maxcost12 = SolutionUCP->Cost;
   if ( i!=0 ) everagecost12 += SolutionUCP->Cost;

   if ( i==9 ) {
		everagecost12 = everagecost12/10;
   }
   Release (SolutionUCP);
   Release(CM10);

  }

  timex12 = GetMyCPUTime();
  printf("Positiv Servit heuristika trvala %f .",timex12-timex11);
  fprintf(NAME, "%2.8f    \t ",timex12-timex11);
  printf("\n Cena nejlepsiho reseni je: %d \n nejhorsiho: %d \n prumerneho: %f. \n\n",mincost12,maxcost12,everagecost12);
  fprintf(NAME, "%2.0d  \t %2.0d \t  %2.8f\n",mincost12,maxcost12,everagecost12);
  printf("---------------------------\n\n");
  //fprintf(NAME, "---------------------------\n\n");

  fclose(NAME);


/////////////////////////////////////////////
/*
   NAME=fopen ( OutputFile,"at");
   NumCalls=0;
   printf ( "Solwing by B&B with Limit Lower Bound computation\n");
//   fprintf (NAME, "Solwing by B&B with Limit Lower Bound computation\n");
   SolutionUCP=Init();

   BABLLB ( CM2,SolutionUCP );
   timex13 = GetMyCPUTime();
   printf("BABLLB trval %f .",timex13-timex);
//   fprintf(NAME, "BABLLB trval %f .",timex13-timex);
   fprintf(NAME, "%f \t",timex13-timex);

//   fprintf (NAME,"\nSolution computed by B&B with LLB, Number of calls B&B %lu\n",NumCalls);
   fprintf (NAME," %lu \t %lu \t",NumCalls,SolutionUCP->Cost );
   printf ("\nSolution computed by B&B with LLB, Number of calls B&B %lu a cena byla %lu \n",NumCalls,SolutionUCP->Cost);
   PrintSolution(SolutionUCP);
// printf("Ubound je %d ",uBound);
   Release (SolutionUCP);
   Release (CM2);
   fclose(NAME);

*/
///////////////////////////////////////
/*
   NAME=fopen ( OutputFile,"at");
   printf ( "Solving by B&B with AURA computation\n");
 //  fprintf (NAME, "Solving by B&B with AURA computation\n");
   NumCalls=0;
   SolutionUCP=Init();
   uBound=MaxCost;
  
   AURA ( CM3,SolutionUCP );
   timex14 = GetMyCPUTime();
   printf("Aura trvala %f .",timex14-timex);
//   fprintf(NAME, "Aura trvala %f .",timex14-timex13);
   fprintf(NAME, "%f \t",timex14-timex);

//   fprintf (NAME,"\nSolution computed by B&B with AURA, Number of calls B&B %lu\n",NumCalls);
   fprintf (NAME," %lu \t %lu \n",NumCalls,SolutionUCP->Cost );
   printf ("\nSolution computed by B&B with AURA, Number of calls B&B %lu a cena byla %lu \n",NumCalls,SolutionUCP->Cost);
   PrintSolution(SolutionUCP);
// printf("Ubound je %d ",uBound);
   Release (SolutionUCP);
   Release(CM3);
   fclose(NAME);

*/
/////////////////////////////////////////////




   delete [] Cm->Mat;
return 0;
}
