Changes

std::vector<Selectionuint16_t> rowMinimarowMins(matrixSize); std::vector<Selectionuint16_t> colMinimacolMins(matrixSize);

findRowMinimafor (rowMinima, zeroInColumnint row = 0; row < matrixSize; row++) { int16_t minimum = findRowMinimum(row); rowMins[row] = minimum; if(minimum != UINT16_MAX) lowerBound += sumMinimaminimum; } for (int row = 0; row < matrixSize; row++) { if (rowMinimarowMins[row] != UINT16_MAX && rowMins[row] != 0);{ subtractMinima subtractRowMinimum(rowMinimarowMins[row], truerow); } findColMinima}  for (int col = 0; col < matrixSize; col++) { int16_t minimum = findColMinimum(colMinima, zeroInColumncol); colMins[col] = minimum; if (minimum != UINT16_MAX) lowerBound += sumMinimaminimum; } for (int col = 0; col < matrixSize; col++) { if (colMinimacolMins[col] != UINT16_MAX && colMins[col] != 0);{ subtractMinima subtractRowMinimum(colMinimacolMins[col], falsecol); } } gatherZeroes(rowMinima, colMinima, zeroes);

free(workingCopyoriginalMatrix); }  int16_t findColMinimum(int col) { cilk::reducer< cilk::op_min<uint16_t> > best; cilk_for(int row = 0; row< matrixSize; row++) { best->calc_min(originalMatrix[row*matrixSize + col]); } return best.get_value(); }  int16_t findRowMinimum(int row) { cilk::reducer< cilk::op_min<uint16_t> > best; cilk_for (int col = 0; col < matrixSize; col++) { best->calc_min(originalMatrix[row*matrixSize + col]); } return best.get_value(); }  void subtractRowMinimum(uint16_t val, int row) { if (val != 0) { cilk_for(int col = 0; col < matrixSize; col++) { if (originalMatrix[row*matrixSize + col] != UINT16_MAX) originalMatrix[row*matrixSize + col] -= val; } } }  void subtractColMinimum(uint16_t val, int col) { if (val != 0) { cilk_for(int row = 0; row < matrixSize; row++) { if (originalMatrix[row*matrixSize + col] != UINT16_MAX) originalMatrix[row*matrixSize + col] -= val; } }

//void createWorkingCopy() { workingCopy // originalMatrix = (uint16_t*)malloc(sizeof(uint16_t) * matrixSize * matrixSize); // memcpy(workingCopyoriginalMatrix, originalMatrix, (sizeof(uint16_t) * matrixSize * matrixSize)); }  void findRowMinima(std::vector<Selection>& rowMinima, std::vector<bool>& zeroInColumn) { for (int row = 0; row < matrixSize; row++) { int rowOffset = row * matrixSize; uint16_t currentMinimum = UINT16_MAX; Selection currentSelection; for (int col = 0; col < matrixSize; col++) { if (workingCopy[rowOffset + col] < currentMinimum) { currentMinimum = workingCopy[rowOffset + col]; currentSelection = Selection(row, col, currentMinimum); zeroInColumn[col] = true; } } if (currentMinimum != UINT16_MAX) { rowMinima.push_back(currentSelection); } } //std::for_each(rowMinima.begin(), rowMinima.end(), [&](Selection s) { // std::cout << " ( " << s.row << ", " << s.col << ") val = " << s.val << " \n"; //});  }  int sumMinima(const std::vector<Selection>& minima) { int sum_of_elems = 0; std::for_each(minima.begin(), minima.end(), [&](Selection s) { sum_of_elems += s.val; }); return sum_of_elems; }  void subtractMinima(std::vector<Selection> minima, const bool row) { if (row) { std::for_each(minima.begin(), minima.end(), [&](Selection s) { if (s.val != 0) { for (int j = 0; j < matrixSize; j++) { if (workingCopy[s.row*matrixSize + j] != UINT16_MAX) { workingCopy[s.row*matrixSize + j] -= s.val; } } } }); } else { std::for_each(minima.begin(), minima.end(), [&](Selection s) { if (s.val != 0) { for (int row = 0; row < matrixSize; row++) { if (workingCopy[row*matrixSize + s.col] != UINT16_MAX) { workingCopy[row*matrixSize + s.col] -= s.val; } } } }); } }  void findColMinima(std::vector<Selection>& colMinima, const std::vector<bool>& zeroInColumn) { for (int col = 0; col < matrixSize; col++) { if (!zeroInColumn[col]) { uint16_t currentMinimum = UINT16_MAX; Selection currentSelection; for (int row = 0; row < matrixSize; row++) { if (workingCopy[row*matrixSize + col] < currentMinimum) { currentMinimum = workingCopy[row*matrixSize + col]; currentSelection = Selection(row, col, currentMinimum); } } if (currentMinimum != UINT16_MAX) { colMinima.push_back(currentSelection); } } } //std::for_each(colMinima.begin(), colMinima.end(), [&](Selection s) { // std::cout << " ( " << s.row << ", " << s.col << ") val = " << s.val << " \n"; //}); }

std::cout << workingCopyoriginalMatrix[i*matrixSize + j] << " ";

void gatherZeroes(std::vector<Selection>& rowMinima, std::vector<Selection>& colMinima, std::vector<Zero>& zeroes) {

if (workingCopyoriginalMatrix[i*matrixSize + j] == 0) {

if (col != z.col && workingCopyoriginalMatrix[z.row*matrixSize + col] < horizontalMin) { horizontalMin = workingCopyoriginalMatrix[z.row*matrixSize + col];

if (row != z.row && workingCopyoriginalMatrix[row * matrixSize + z.col] < verticalMin) { verticalMin = workingCopyoriginalMatrix[row * matrixSize + z.col];

int amountOfCities = 15500;