Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "conio.h"
- #include "iostream"
- #include "iomanip"
- #include "vector"
- using namespace std;
- vector<int> ConstPrived;//сума констант приведення
- vector<int>rowIndex;
- vector<int>columnIndex;
- vector<int>rowMin;
- vector<int>columnMin;
- vector<int>SumRowColumnMin;
- int indexI = 0, indexJ = 0;
- const int Row = 5, Column = 5;
- int Symbol = -1;
- int RowCount = Row, ColumnCount = Column;
- int FirstArray[Row][Column] =
- {
- { -1,48,27,31,43 },
- { 33,-1,28,44,43 },
- { 41,28,-1,40,36 },
- { 37,35,29,-1,46 },
- { 48,48,25,29,-1 }
- };
- void ShowArray(int **Array,int row,int column)
- {
- cout << endl;
- for (int i = 0; i < row; i++)
- {
- for (int j = 0; j < column; j++)
- {
- if (Array[i][j] == (Symbol))
- cout << setw(4) << (Array[i][j]) << " ";
- else
- cout <<setw(4)<< Array[i][j] << " ";
- }
- cout << endl;
- }
- cout << endl;
- }
- void* MinRowColumnArray(int **BigArray, int row, int column,int *SmallArray, bool flag)
- {
- if (flag==0)
- {
- for (int i = 0; i < row; i++)
- {
- int min = 9999;
- int mint =min;
- for (int j = 0; j < column; j++)
- {
- if (((*(*(BigArray + i) + j)) >= 0))
- {
- if ((*(*(BigArray + i) + j)) < min)
- min = (*(*(BigArray + i) + j));
- }
- else if ((*(*(BigArray + i) + j) == Symbol))
- {
- if (j==(column-1)&&(min==mint))
- min = 0;
- }
- }
- *(SmallArray + i) = min;
- }
- return SmallArray;
- }
- else if (flag == 1)
- {
- for (int j = 0; j < Column; j++)
- {
- int min = 9999;
- int mint = min;
- for (int i = 0; i < Row; i++)
- {
- if (((*(*(BigArray + i) + j)) >= 0))
- {
- if ((*(*(BigArray + i) + j) < min))
- {
- min = (*(*(BigArray + i) + j));
- }
- }
- else if ((*(*(BigArray + i) + j) == Symbol))
- {
- if (i == (Row - 1) && (min == mint))
- min = 0;
- }
- }
- *(SmallArray+j) = min;
- }
- return SmallArray;
- }
- }
- int ** MinusRowColumnHAR(int **BigArray, int row, int column, int *SmallArray, bool flag)
- {
- if (flag == 0) {
- for (int i = 0; i < row; i++)
- for (int j = 0; j < column; j++)
- {
- if ((*(*(BigArray + i) + j)) == (Symbol))
- continue;
- else
- {
- (*(*(BigArray + i) + j)) = ((*(*(BigArray + i) + j)) - (*(SmallArray + i)));
- }
- }
- return BigArray;
- }
- else if (flag == 1)
- {
- for (int i = 0; i < row; i++)
- for (int j = 0; j < column; j++)
- {
- if ((*(*(BigArray + j) + i)) == (Symbol))
- continue;
- else
- {
- (*(*(BigArray + j) + i)) = ((*(*(BigArray + j) + i)) - (*(SmallArray + i)));
- }
- }
- return BigArray;
- }
- }
- void SumConst(int *RowArray, int *ColumnArray,int count,int indexVect, bool flag=0)
- {
- int Sum = 0;
- for (int i = 0; i < count; i++)
- Sum = Sum + (*(RowArray + i)) + (*(ColumnArray + i));
- if (flag == 0)
- ConstPrived.push_back(Sum);
- else if (flag == 1)
- {
- ConstPrived.push_back(ConstPrived[indexVect] + Sum);
- }
- }
- void ZerosIndex(int** BigArray,int row,int column)
- {
- for (int i = 0; i<row; i++)
- for (int j = 0; j < column; j++)
- if ((*(*(BigArray+i)+j))== 0)
- {
- rowIndex.push_back(i);
- columnIndex.push_back(j);
- }
- }
- void MinElementRowToZero(int **BigArray, int row,int column)
- {
- int min = 0;
- for (int i = 0; i <columnIndex.size(); i++)
- {
- indexI =rowIndex[i];
- indexJ =columnIndex[i];
- min = 9999;
- for (int j = 0; j < row; j++)
- {
- if (((*(*(BigArray+indexI)+j)) >= 0) && (indexJ != j))
- {
- if (((*(*(BigArray+indexI)+j)) < min))
- {
- min = (*(*(BigArray+indexI)+j));
- }
- }
- else if ((*(*(BigArray+indexI)+j)) == (Symbol))
- continue;
- }
- rowMin.push_back(min);
- }
- min = 0;
- for (int i = 0; i <rowIndex.size(); i++)
- {
- indexI =rowIndex[i];
- indexJ =columnIndex[i];
- min = 9999;
- for (int j = 0; j < column; j++)
- {
- if (((*(*(BigArray+j)+indexJ)) >= 0) && (indexI != j))
- {
- if (((*(*(BigArray+j)+indexJ)) < min))
- {
- min = (*(*(BigArray+j)+indexJ));
- }
- }
- else if ((*(*(BigArray+j)+indexJ)) ==(Symbol))
- continue;
- }
- columnMin.push_back(min);
- }
- }
- void DelRowColumn(int **BigArray, int row, int column,int rowdel,int columndel)
- {
- for(int i=0;i<row;i++)
- for (int j = 0; j < column; j++)
- {
- if (i == rowdel)
- (*(*(BigArray + i) + j)) = Symbol;
- else if (i == columndel)
- (*(*(BigArray + j) + i)) = Symbol;
- }
- RowCount--;
- ColumnCount--;
- }
- void main()
- {
- int** Array = new int *[Row];
- for (int i = 0; i < Row; ++i)
- Array[i] = new int[Column];//головний масив
- // int** ArrayTemp = new int *[Row];
- //for (int i = 0; i < (RowCount-1); ++i)
- // ArrayTemp[i] = new int[ColumnCount-1];//допоміжний масив для видалення рядка/стовпця
- int *rowTemp = new int[Row];//рахуємо необхідні значення по рядках
- int *columnTemp = new int[Column];//рахуємо необхідні значення по стовпцях
- for (int i = 0; i < Row; i++)
- for (int j = 0; j < Column; j++)
- {
- (i == j) ? Array[i][j] = Symbol : Array[i][j] = FirstArray[i][j];
- }
- ShowArray(Array, Row, Column);
- MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
- MinusRowColumnHAR(Array, Row, Column, rowTemp, 0);//віднімаємо
- MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
- MinusRowColumnHAR(Array, Row, Column, columnTemp, 1);//віднімаємо
- int temp = 0;
- SumConst(rowTemp, columnTemp, Row, 0);//first
- ShowArray(Array, Row, Column);
- while(temp<Row)
- {
- //1 крок визнчааємо Ребро вітвлення
- ZerosIndex(Array, Row, Column);
- MinElementRowToZero(Array, Row, Column);
- //1 крок Виключення ребра
- for (int i = 0; i < columnMin.size(); i++)
- SumRowColumnMin.push_back(columnMin[i] + rowMin[i]);
- int max = 0;
- for (int i = 0; i < columnMin.size(); i++)
- {
- if (SumRowColumnMin[i] > max)
- {
- max = SumRowColumnMin[i];
- indexI = rowIndex[i];
- indexJ = columnIndex[i];
- }
- }
- rowIndex[temp] = indexI;
- columnIndex[temp] = indexJ;
- temp++;
- Array[indexI][indexJ] = (Symbol);
- MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
- MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
- ShowArray(Array, Row, Column);
- SumConst(rowTemp, columnTemp, Row, 0, 1);
- //1 крок Включення ребра/// Замінимо необхідні стовпці та рядки ~ бо видаляти ліньки
- DelRowColumn(Array, Row, Column, indexI, indexJ);
- ShowArray(Array, Row, Column);
- MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
- MinusRowColumnHAR(Array, Row, Column, rowTemp, 0);//віднімаємо
- MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
- MinusRowColumnHAR(Array, Row, Column, columnTemp, 1);//віднімаємо
- SumConst(rowTemp, columnTemp, Row, 0, 1);
- ShowArray(Array, Row, Column);
- for (int i = 0; i < Row; i++)
- cout << rowIndex[i] << " ";
- cout << endl;
- for (int i = 0; i < Column; i++)
- cout << columnIndex[i] << " ";
- cout << endl;
- for (int i = temp; i < ConstPrived.size() - 1; i++)
- {
- if (ConstPrived[i] > ConstPrived[i + 1])
- {
- ConstPrived[i] = ConstPrived[i + 1];
- ConstPrived[i + 1] = 0;
- }
- else
- {
- ConstPrived[i + 1] = 0;
- }
- }
- }
- delete[]rowTemp;
- delete[]columnTemp;
- for (int i = 0; i < Row; i++)
- {
- delete[]Array[i]; // удаляются сами объекты
- }
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement