Advertisement
Guest User

Я ЕБАЛ ВСЕ ЭТО В РОТ!!!

a guest
Sep 28th, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.64 KB | None | 0 0
  1. #include "conio.h"
  2. #include "iostream"
  3. #include "iomanip"
  4. #include "vector"
  5. using namespace std;
  6. vector<int> ConstPrived;//сума констант приведення
  7. vector<int>rowIndex;
  8. vector<int>columnIndex;
  9. vector<int>rowMin;
  10. vector<int>columnMin;
  11. vector<int>SumRowColumnMin;
  12. int indexI = 0, indexJ = 0;
  13. const int Row = 5, Column = 5;
  14. int Symbol = -1;
  15. int RowCount = Row, ColumnCount = Column;
  16. int FirstArray[Row][Column] =
  17. {
  18.     { -1,48,27,31,43 },
  19.     { 33,-1,28,44,43 },
  20.     { 41,28,-1,40,36 },
  21.     { 37,35,29,-1,46 },
  22.     { 48,48,25,29,-1 }
  23. };
  24. void ShowArray(int **Array,int row,int column)
  25. {
  26.     cout << endl;
  27.     for (int i = 0; i < row; i++)
  28.     {
  29.         for (int j = 0; j < column; j++)
  30.         {
  31.             if (Array[i][j] == (Symbol))
  32.                 cout << setw(4) << (Array[i][j]) << " ";
  33.             else
  34.                 cout <<setw(4)<< Array[i][j] << " ";
  35.         }
  36.         cout << endl;
  37.     }
  38.     cout << endl;
  39. }
  40. void* MinRowColumnArray(int **BigArray, int row, int column,int *SmallArray, bool flag)
  41. {
  42.     if (flag==0)
  43.     {
  44.         for  (int i = 0; i < row; i++)
  45.         {
  46.             int min = 9999;
  47.             int mint =min;
  48.             for (int j = 0; j < column; j++)
  49.             {
  50.                 if (((*(*(BigArray + i) + j)) >= 0))
  51.                 {
  52.                     if ((*(*(BigArray + i) + j)) < min)
  53.                         min = (*(*(BigArray + i) + j));
  54.                 }
  55.                 else if ((*(*(BigArray + i) + j) == Symbol))
  56.                 {
  57.                     if (j==(column-1)&&(min==mint))
  58.                         min = 0;
  59.                 }
  60.  
  61.             }
  62.             *(SmallArray + i) = min;
  63.         }
  64.         return SmallArray;
  65.     }
  66.     else if (flag == 1)
  67.     {
  68.         for (int j =    0; j < Column; j++)
  69.         {
  70.             int min = 9999;
  71.             int mint = min;
  72.             for  (int i = 0; i < Row; i++)
  73.             {
  74.                 if (((*(*(BigArray + i) + j)) >= 0))
  75.                 {
  76.                     if ((*(*(BigArray + i) + j) < min))
  77.                     {
  78.                         min = (*(*(BigArray + i) + j));
  79.                     }
  80.                 }
  81.                 else if ((*(*(BigArray + i) + j) == Symbol))
  82.                 {
  83.                     if (i == (Row - 1) && (min == mint))
  84.                         min = 0;
  85.                 }
  86.            
  87.             }
  88.             *(SmallArray+j) = min;
  89.         }
  90.         return SmallArray;
  91.     }
  92. }
  93. int ** MinusRowColumnHAR(int **BigArray, int row, int column, int *SmallArray, bool flag)
  94. {
  95.     if (flag == 0) {
  96.         for (int i = 0; i < row; i++)
  97.             for (int j = 0; j < column; j++)
  98.             {
  99.                 if ((*(*(BigArray + i) + j)) == (Symbol))
  100.                     continue;
  101.                 else
  102.                 {
  103.  
  104.                     (*(*(BigArray + i) + j)) = ((*(*(BigArray + i) + j)) - (*(SmallArray + i)));
  105.  
  106.                 }
  107.             }
  108.         return BigArray;
  109.     }
  110.     else if (flag == 1)
  111.     {
  112.         for (int i = 0; i < row; i++)
  113.             for (int j = 0; j < column; j++)
  114.             {
  115.                 if ((*(*(BigArray + j) + i)) == (Symbol))
  116.                     continue;
  117.                 else
  118.                 {
  119.                     (*(*(BigArray + j) + i)) = ((*(*(BigArray + j) + i)) - (*(SmallArray + i)));
  120.  
  121.                 }
  122.             }
  123.         return BigArray;
  124.     }
  125. }
  126. void SumConst(int *RowArray, int *ColumnArray,int count,int indexVect, bool flag=0)
  127. {
  128.         int Sum = 0;
  129.         for (int i = 0; i < count; i++)
  130.             Sum = Sum + (*(RowArray + i)) + (*(ColumnArray + i));
  131.         if (flag == 0)
  132.         ConstPrived.push_back(Sum);
  133.         else if (flag == 1)
  134.         {
  135.             ConstPrived.push_back(ConstPrived[indexVect] + Sum);
  136.         }
  137. }
  138. void ZerosIndex(int** BigArray,int row,int column)
  139. {
  140.     for (int i = 0; i<row; i++)
  141.         for (int j = 0; j < column; j++)
  142.             if ((*(*(BigArray+i)+j))== 0)
  143.             {
  144.                 rowIndex.push_back(i);
  145.                 columnIndex.push_back(j);
  146.             }
  147. }
  148. void MinElementRowToZero(int **BigArray, int row,int column)
  149. {
  150.     int min = 0;
  151.     for (int i = 0; i <columnIndex.size(); i++)
  152.     {
  153.         indexI =rowIndex[i];
  154.         indexJ =columnIndex[i];
  155.  
  156.          min = 9999;
  157.         for (int j = 0; j < row; j++)
  158.         {
  159.  
  160.             if (((*(*(BigArray+indexI)+j)) >= 0) && (indexJ != j))
  161.             {
  162.                 if (((*(*(BigArray+indexI)+j)) < min))
  163.                 {
  164.                     min = (*(*(BigArray+indexI)+j));
  165.  
  166.                 }
  167.             }
  168.             else if ((*(*(BigArray+indexI)+j)) == (Symbol))
  169.                 continue;
  170.  
  171.         }
  172.         rowMin.push_back(min);
  173.     }
  174.     min = 0;
  175.     for (int i = 0; i <rowIndex.size(); i++)
  176.     {
  177.         indexI =rowIndex[i];
  178.         indexJ =columnIndex[i];
  179.         min = 9999;
  180.         for (int j = 0; j < column; j++)
  181.         {
  182.  
  183.             if (((*(*(BigArray+j)+indexJ)) >= 0) && (indexI != j))
  184.             {
  185.                 if (((*(*(BigArray+j)+indexJ)) < min))
  186.                 {
  187.                     min = (*(*(BigArray+j)+indexJ));
  188.  
  189.                 }
  190.             }
  191.             else if ((*(*(BigArray+j)+indexJ)) ==(Symbol))
  192.                 continue;
  193.  
  194.         }
  195.         columnMin.push_back(min);
  196.     }
  197. }
  198. void DelRowColumn(int **BigArray, int row, int column,int rowdel,int columndel)
  199. {
  200.     for(int i=0;i<row;i++)
  201.         for (int j = 0; j < column; j++)
  202.         {
  203.             if (i == rowdel)
  204.                 (*(*(BigArray + i) + j)) = Symbol;
  205.             else if (i == columndel)
  206.                 (*(*(BigArray + j) + i)) = Symbol;
  207.         }
  208.     RowCount--;
  209.     ColumnCount--;
  210. }
  211. void main()
  212. {
  213.     int** Array = new int *[Row];
  214.     for (int i = 0; i < Row; ++i)
  215.         Array[i] = new int[Column];//головний масив
  216. //  int** ArrayTemp = new int *[Row];
  217.     //for (int i = 0; i < (RowCount-1); ++i)
  218.     //  ArrayTemp[i] = new int[ColumnCount-1];//допоміжний масив для видалення рядка/стовпця
  219.     int *rowTemp = new int[Row];//рахуємо необхідні значення по рядках
  220.     int *columnTemp = new int[Column];//рахуємо необхідні значення по стовпцях
  221.  
  222.     for (int i = 0; i < Row; i++)
  223.         for (int j = 0; j < Column; j++)
  224.         {
  225.             (i == j) ? Array[i][j] = Symbol : Array[i][j] = FirstArray[i][j];
  226.         }
  227.     ShowArray(Array, Row, Column);
  228.     MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
  229.     MinusRowColumnHAR(Array, Row, Column, rowTemp, 0);//віднімаємо
  230.     MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
  231.     MinusRowColumnHAR(Array, Row, Column, columnTemp, 1);//віднімаємо
  232.     int temp = 0;
  233.     SumConst(rowTemp, columnTemp, Row, 0);//first
  234.     ShowArray(Array, Row, Column);
  235. while(temp<Row)
  236.     {
  237.             //1 крок визнчааємо Ребро вітвлення
  238.     ZerosIndex(Array, Row, Column);
  239.     MinElementRowToZero(Array, Row, Column);
  240.  
  241.     //1 крок Виключення ребра
  242.     for (int i = 0; i < columnMin.size(); i++)
  243.         SumRowColumnMin.push_back(columnMin[i] + rowMin[i]);
  244.     int max = 0;
  245.     for (int i = 0; i < columnMin.size(); i++)
  246.     {
  247.         if (SumRowColumnMin[i] > max)
  248.         {
  249.             max = SumRowColumnMin[i];
  250.             indexI = rowIndex[i];
  251.             indexJ = columnIndex[i];
  252.         }
  253.     }
  254.  
  255.     rowIndex[temp] = indexI;
  256.     columnIndex[temp] = indexJ;
  257.     temp++;
  258.     Array[indexI][indexJ] = (Symbol);
  259.  
  260.  
  261.     MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
  262.     MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
  263.     ShowArray(Array, Row, Column);
  264.     SumConst(rowTemp, columnTemp, Row, 0, 1);
  265.  
  266.     //1 крок Включення ребра/// Замінимо необхідні стовпці та рядки ~ бо видаляти ліньки
  267.     DelRowColumn(Array, Row, Column, indexI, indexJ);
  268.     ShowArray(Array, Row, Column);
  269.     MinRowColumnArray(Array, Row, Column, rowTemp, 0);// мінімальне по рядках
  270.     MinusRowColumnHAR(Array, Row, Column, rowTemp, 0);//віднімаємо
  271.     MinRowColumnArray(Array, Row, Column, columnTemp, 1);//мінімальне по стовпцях
  272.     MinusRowColumnHAR(Array, Row, Column, columnTemp, 1);//віднімаємо
  273.     SumConst(rowTemp, columnTemp, Row, 0, 1);
  274.     ShowArray(Array, Row, Column);
  275.  
  276.  
  277.     for (int i = 0; i < Row; i++)
  278.         cout << rowIndex[i] << " ";
  279.     cout << endl;
  280.     for (int i = 0; i < Column; i++)
  281.         cout << columnIndex[i] << " ";
  282.     cout << endl;
  283.  
  284.     for (int i = temp; i < ConstPrived.size() - 1; i++)
  285.     {
  286.         if (ConstPrived[i] > ConstPrived[i + 1])
  287.         {
  288.             ConstPrived[i] = ConstPrived[i + 1];
  289.             ConstPrived[i + 1] = 0;
  290.         }
  291.         else
  292.         {
  293.             ConstPrived[i + 1] = 0;
  294.         }
  295.     }
  296.    
  297. }
  298.  
  299.     delete[]rowTemp;
  300.     delete[]columnTemp;
  301.  
  302.     for (int i = 0; i < Row; i++)
  303.     {
  304.         delete[]Array[i]; // удаляются сами объекты
  305.     }
  306.     system("pause");
  307. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement