Komivoyazher/Komivoyaz/Komivoyazh.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Komivoyaz
{
    class MetodKomivoyazher
    {
        public int Komivoyzher(int[,] matrix, int size, int[] dj, int[] di, int[,] outputMatrix)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    matrix[i, j] = outputMatrix[i, j];
                }
            }

            int lowerBorder = 0;
            int[] rows = new int[size];
            int[] columns = new int[size];

            for (int i = 0; i < size; i++)
            {
                rows[i] = i;
                columns[i] = i;
            }

            while (matrix.GetLength(0) > 1)
            {
                int[,] constants = new int[matrix.GetLength(1), matrix.GetLength(0)]; 
                di = new int[size]; //массив минимумов строк
                dj = new int[size]; //массив минимумов столбцов
                int minElimentReducton = int.MaxValue;

                //редукция 
                for (int i = 0; i < matrix.GetLength(0); i++)
                {
                    minElimentReducton = int.MaxValue;
                    for (int j = 0; j < matrix.GetLength(1); j++)
                    {
                        if (matrix[i, j] < minElimentReducton)
                        {
                            minElimentReducton = matrix[i, j];
                        }
                    }
                    di[i] = minElimentReducton;
                }

                for (int i = 0; i < matrix.GetLength(0); i++)
                {
                    for (int j = 0; j < matrix.GetLength(1); j++)
                    {
                        if (matrix[i, j] != int.MaxValue)
                        {
                            matrix[i, j] -= di[i];
                        }
                    }
                }

                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    minElimentReducton = int.MaxValue;
                    for (int i = 0; i < matrix.GetLength(0); i++)
                    {
                        if (matrix[i, j] < minElimentReducton)
                        {
                            minElimentReducton = matrix[i, j];
                        }
                    }
                    dj[j] = minElimentReducton;
                }

                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    for (int i = 0; i < matrix.GetLength(0); i++)
                    {
                        if (matrix[i, j] != int.MaxValue)
                        {
                            matrix[i, j] -= dj[j];
                        }
                    }
                }

                lowerBorder += di.Sum() + dj.Sum(); //нулевая граница

                for (int i = 0; i < matrix.GetLength(0); i++)
                {
                    for (int j = 0; j < matrix.GetLength(1); j++)
                    {
                        if (matrix[i, j] == 0)
                        {
                            //коэфиценты нулевых ячеек
                            constants[i, j] = MinEl(Column(matrix, j), Column(matrix, j).Length, i) + MinEl(Row(matrix, i), Row(matrix, i).Length, j);
                        }
                    }
                }

                int minCoeffI = 0;
                int minCoeffJ = 0;
                int maxElementCoeff = int.MinValue;

                for (int i = constants.GetLength(0) - 1; i >= 0; i--)
                {
                    for (int j = constants.GetLength(1) - 1; j >= 0; j--)
                    {
                        if (constants[i, j] >= maxElementCoeff)
                        {
                            maxElementCoeff = constants[i, j];
                            minCoeffI = i;
                            minCoeffJ = j;
                        }
                    }
                }

                Console.WriteLine(rows[minCoeffI]);
                Console.WriteLine(columns[minCoeffJ]);


                try
                {
                    //"М"
                    matrix[Array.IndexOf(rows, columns[minCoeffJ]), Array.IndexOf(columns, rows[minCoeffI])] = int.MaxValue;
                }
                catch { }

                //матрица вспомогательная
                int[,] matrix2 = new int[--size, size];
                for (int i = 0, i1 = 0; i < size && i1 < size + 1; i++, i1++)
                {
                    for (int j = 0, j1 = 0; j < size && j1 < size + 1; j++, j1++)
                    {
                        if (minCoeffI == i1) i1++;
                        if (minCoeffJ == j1) j1++;
                        matrix2[i, j] = matrix[i1, j1];
                    }
                }

                //копирование матрицы в текущую
                matrix = matrix2.Clone() as int[,];

                int[] remRows = new int[size];
                int[] remColumns = new int[size];

                //вычеркивание из матрицы лишних строк
                for (int i = 0, i1 = 0; i < size && i1 < size + 1; i++, i1++)
                {
                    if (minCoeffI == i1) i1++;
                    remRows[i] = rows[i1];
                }

                for (int j = 0, j1 = 0; j < size && j1 < size + 1; j++, j1++)
                {
                    if (minCoeffJ == j1) j1++;
                    remColumns[j] = columns[j1];
                }

                columns = new int[size];
                Array.Copy(remColumns, columns, remColumns.Length);
                rows = new int[size];
                Array.Copy(remRows, rows, remRows.Length);
            }

            return lowerBorder;
        }
        int[] Row(int[,] matrix, int i)
        {
            int[] Row = new int[matrix.GetLength(0)];
            for (int j = 0; j < Row.Length; j++)
            {
                Row[j] = matrix[i, j];
            }
            return Row;
        }

        int[] Column(int[,] matrix, int j)
        {
            int[] Column = new int[matrix.GetLength(1)];
            for (int i = 0; i < Column.Length; i++)
            {
                Column[i] = matrix[i, j];
            }
            return Column;
        }

        int MinEl(int[] arr, int len, int ind)
        {
            int min = int.MaxValue;
            for (int i = 0; i < len; i++)
            {
                if (i == ind) continue;
                if (min > arr[i]) min = arr[i];
            }
            return min;
        }
    }
}