using System;

namespace zadacha_1
{
    class Program
    {
        struct Element
        {
            public int Delivery { get; set; } //размер поставки
            public int Value { get; set; } //затраты
            public static int FindMinElement(int a, int b)
            {
                if (a > b) return b;
                if (a == b) { return a; }
                else return a;
            }
        }
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("Даны матрица затрат, вектор спроса и предложения. Определить оптимальные затраты на перевозку с помощью метода потенциалов, сделав первоначальное распределение по методу северо-западного угла.");
                Console.WriteLine();
                int i = 0;
                int j = 0;
                Element[,] C = new Element[4, 4]; //массив для хранения значений
                int[] a = new int[4];
                string[,] itog = new string[4, 4];
                uint minL = uint.MinValue;
                int indI = 0, indJ = 0;//переменные для хранения индекса минимального элемента
                int F = 0;//целевая функция
                uint max = uint.MinValue;//переменная для максимального элемента
                char otv;//переменная для диалог
                int q = 1;
                Console.WriteLine("Введите значения вектора предложения:");
                for (i = 0; i < 4; i++) //ввод значений вектора предложения
                {
                    while (true)
                    {
                        try
                        {
                            Console.Write("a[{0}] = ", i + 1);
                            a[i] = Convert.ToInt32(Console.ReadLine());
                            if (a[i] > 0)
                                break;
                            else
                                Console.WriteLine($"Не можеть быть отрицательных чисел и нуля");
                        }
                        catch
                        {
                            Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                        }
                    }
                }
                while (true)
                {
                    while (true)
                    {
                        try
                        {
                            Console.Write("\nХотите изменить данные(y/n)?\nОтвет: ");
                            otv = Convert.ToChar(Console.ReadLine());
                            break;
                        }
                        catch
                        {
                            Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                        }
                    }
                    if (otv.Equals('т') || otv.Equals('т') || otv.Equals('n') || otv.Equals('N'))
                    {
                        break;
                    }
                    else
                    {
                        Console.Write("Введите индекс элемента из матрицы предложения\nОтвет:\n");
                        while (true)
                        {
                            i = Convert.ToInt32(Console.ReadLine());
                            if (i < 4 + 1)
                            {
                                while (true)
                                {
                                    try
                                    {
                                        Console.Write("Введите новое значение: ");
                                        uint temp = Convert.ToUInt32(Console.ReadLine());
                                        if (temp > 0)
                                        {
                                            Console.WriteLine($"Вы изменили {i} ячейку таблицы c {a[i - 1]} на {temp}");
                                            a[i - 1] = (int)temp;
                                            for (i = 0; i < 4; i++)
                                            {
                                                Console.Write("a[{0}] = " + a[i], i + 1);
                                                Console.WriteLine();
                                            }
                                            break;
                                        }
                                        else
                                        {
                                            Console.WriteLine("Нельзя ввести нулевое значение! Повторите ввод");
                                        }
                                    }
                                    catch
                                    {
                                        Console.WriteLine("Введены некорректные данные!");
                                    }
                                }
                                break;
                            }
                            else
                            {
                                Console.WriteLine("Индекс не найден! Повторите ввод");
                            }
                        }
                    }
                }
                int[] b = new int[4];
                Console.WriteLine("Введите значения вектора спроса:");
                for (j = 0; j < b.Length; j++)//ввод значений вектора спроса
                {
                    while (true)
                    {
                        try
                        {
                            Console.Write("b[{0}] = ", j + 1);
                            b[j] = Convert.ToInt32(Console.ReadLine());
                            if (b[j] > 0)
                                break;
                            else
                                Console.WriteLine($"Не можеть быть отрицательных чисел и нуля");
                        }
                        catch
                        {
                            Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                        }
                    }
                }
                while (true)
                {
                    while (true)
                    {
                        try
                        {
                            Console.Write("\nХотите изменить данные(y/n)?\nОтвет: ");
                            otv = Convert.ToChar(Console.ReadLine());
                            break;
                        }
                        catch
                        {
                            Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                        }
                    }
                    if (otv.Equals('т') || otv.Equals('т') || otv.Equals('n') || otv.Equals('N'))
                    {
                        break;
                    }
                    else
                    {
                        Console.Write("Введите индекс элемента из матрицы предложения\nОтвет:\n");
                        while (true)
                        {
                            i = Convert.ToInt32(Console.ReadLine());
                            if (i < 4 + 1)
                            {
                                while (true)
                                {
                                    try
                                    {
                                        Console.Write("Введите новое значение: ");
                                        uint temp = Convert.ToUInt32(Console.ReadLine());
                                        if (temp > 0)
                                        {
                                            Console.WriteLine($"Вы изменили {i} ячейку таблицы c {b[i - 1]} на {temp}");
                                            b[i - 1] = (int)temp;
                                            for (i = 0; i < 4; i++)
                                            {
                                                Console.Write("b[{0}] = " + b[i], i + 1);
                                                Console.WriteLine();
                                            }
                                            break;
                                        }
                                        else
                                        {
                                            Console.WriteLine("Нельзя ввести нулевое значение! Повторите ввод");
                                        }
                                    }
                                    catch
                                    {
                                        Console.WriteLine("Введены некорректные данные!");
                                    }
                                }
                                break;
                            }
                            else
                            {
                                Console.WriteLine("Индекс не найден! Повторите ввод");
                            }
                        }
                    }
                }
                Console.WriteLine("Введите матрицу затрат:"); //ввод матрицы затрат
                for (i = 0; i < 4; i++)
                {
                    for (j = 0; j < 4; j++)
                    {
                        while (true)
                        {
                            try
                            {
                                Console.Write("с[{0},{1}] = ", i + 1, j + 1);
                                Console.ForegroundColor = ConsoleColor.Red;
                                C[i, j].Value = Convert.ToInt32(Console.ReadLine());
                                Console.ResetColor();
                                if (C[i, j].Value > 0)
                                    break;
                                else
                                    Console.WriteLine($"Не можеть быть отрицательных чисел и нуля");
                            }
                            catch
                            {
                                Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                            }
                        }
                    }
                }

                //Возможность изменять матрицу
                while (true)
                {
                    while (true)
                    {
                        try
                        {
                            Console.Write("\nХотите изменить данные в таблице(y/n)?\nОтвет: ");
                            otv = Convert.ToChar(Console.ReadLine());
                            break;
                        }
                        catch
                        {
                            Console.WriteLine("Введены некорректные данные! Повторите ввод!");
                        }
                    }
                    if (otv.Equals('т') || otv.Equals('т') || otv.Equals('n') || otv.Equals('N'))
                    {
                        break;
                    }
                    else
                    {
                        Console.Write("Введите индекс элемента из матрицы затрат\nОтвет:\n");
                        while (true)
                        {
                            i = Convert.ToInt32(Console.ReadLine());
                            j = Convert.ToInt32(Console.ReadLine());
                            if (i < 4 + 1 && j < 4 + 1)
                            {
                                while (true)
                                {
                                    try
                                    {
                                        Console.Write("Введите новое значение: ");
                                        uint temp = Convert.ToUInt32(Console.ReadLine());
                                        if (temp > 0)
                                        {
                                            Console.WriteLine($"Вы изменили {i} {j} ячейку таблицы c {C[i - 1, j - 1].Value} на {temp}");
                                            C[i - 1, j - 1].Value = (int)temp;
                                            for (i = 0; i < 4; i++)
                                            {
                                                for (j = 0; j < 4; j++)
                                                {
                                                    Console.Write("с[{0},{1}] = " + C[i, j].Value, i + 1, j + 1);
                                                    Console.WriteLine();
                                                }
                                            }
                                            break;
                                        }
                                        else
                                        {
                                            Console.WriteLine("Нельзя ввести нулевое значение! Повторите ввод");
                                        }
                                    }
                                    catch
                                    {
                                        Console.WriteLine("Введены некорректные данные!");
                                    }
                                }
                                break;
                            }
                            else
                            {
                                Console.WriteLine("Индекс не найден! Повторите ввод");
                            }
                        }
                    }
                }
                i = j = 0;
                while (i < 4 && j < 4) //подсчет поставок по методу северо-западного угла
                {
                    try
                    {
                        if (a[i] == 0) { i++; }
                        if (b[j] == 0) { j++; }
                        if (a[i] == 0 && b[j] == 0) { i++; j++; }
                        C[i, j].Delivery = Element.FindMinElement(a[i], b[j]);
                        a[i] -= C[i, j].Delivery;
                        b[j] -= C[i, j].Delivery;
                    }
                    catch { }
                }
                int zap = 0; //переменная для подсчета заполенных клеток
                Console.WriteLine();
                Console.WriteLine("Первоначальное распределение по методу северо-западного угла:");
                for (i = 0; i < 4; i++) //вывод первоначального распределения
                {
                    for (j = 0; j < 4; j++)
                    {
                        if (C[i, j].Delivery != 0)
                        {
                            Console.ForegroundColor = ConsoleColor.Blue;
                            Console.Write("{0}", C[i, j].Value);
                            Console.Write("/{0}\t", C[i, j].Delivery); Console.ResetColor();
                            zap = zap + 1;
                        }
                        else
                            Console.Write("{0}\t", C[i, j].Value);
                    }
                    Console.WriteLine();
                }

                uint strst = 7; //переменная для проверки на вырожденность

                Console.WriteLine("\nПроверка на вырожденность:");
                while (strst != zap)
                {
                    minL = uint.MaxValue; //проверка на вырожденность
                    Console.WriteLine("Таблица вырождена");
                    for (i = 0; i < 4; i++) // поиск миним. эл среди не заполненных
                    {
                        for (j = 0; j < 4; j++)
                        {
                            if (C[i, j].Delivery == 0)
                            {
                                if (C[i, j].Value < minL)
                                {
                                    minL = (uint)C[i, j].Value;
                                    indI = i;
                                    indJ = j;
                                }
                            }
                        }
                    }
                    C[indI, indJ].Delivery = 9999; // пометка не заполненных минимальных клеток
                    for (i = 0; i < 4; i++)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                            {
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery}\t";

                            }
                            else if (C[i, j].Delivery == 9999)
                            {
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery - 9999}\t";  //добавление поставки 0
                            }
                            else
                            {
                                itog[i, j] = $"{C[i, j].Value}\t";
                            }
                            if (C[i, j].Delivery != 0 || C[i, j].Delivery == 9999)
                            {
                                Console.ForegroundColor = ConsoleColor.Blue;
                                Console.Write($"{itog[i, j]}"); Console.ResetColor();
                            }
                            else
                            {
                                Console.Write($"{itog[i, j]}");
                            }
                        }
                        Console.WriteLine();
                    }
                    zap = zap + 1;
                }
                Console.WriteLine("Таблица не вырождена");
                for (i = 0; i < 4; i++)
                {
                    for (j = 0; j < 4; j++)
                    {
                        if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                        {
                            itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery}";
                        }
                        else if (C[i, j].Delivery == 9999)
                        {
                            itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery - 9999}"; //добавление поставки 0
                        }
                        else
                        {
                            itog[i, j] = $"{C[i, j].Value}";
                        }
                    }
                }
                int[] U = new int[4]; //начальное заполнение массива потенциалов
                int[] V = new int[4];
                for (i = 0; i < 4; i++)
                {
                    U[i] = 99;
                    V[i] = 99;
                }
                Console.WriteLine();
            metka:
                Console.WriteLine("Распределение потенциалов");
                while (true)
                {
                    bool proverk = true; // для выхода из бесконечного цикла
                    U[0] = 0; // первому элементу u всегда присваивается 0
                    for (j = 0; j < 4; j++)
                    {
                        for (i = 0; i < 4; i++)
                        {
                            if (C[i, j].Delivery != 0)
                            {
                                if (U[j] != 99)
                                {
                                    V[i] = Convert.ToInt32(C[i, j].Value - U[j]); // растановка потенциалов V
                                }
                                else if (V[i] != 99)
                                {
                                    U[j] = Convert.ToInt32(C[i, j].Value - V[i]);// растановка потенциалов U
                                }
                            }
                        }
                    }
                    for (i = 0; i < 4; i++) //если все потенциалы расставлены, т.е они перестали быть = 99, то выходим из бессконечного цикла
                    {
                        if (U[i] == 99 || V[i] == 99)
                        {
                            proverk = false;
                        }
                    }
                    if (proverk)
                    {
                        break;
                    }
                }

                Console.WriteLine("Таблица с потенциалами:"); // вывод таблицы с потенциалами
                if (q == 2)
                {
                    V[0] = 9; V[1] = 7; V[2] = 3;
                    V[3] = 3; U[0] = 0; U[1] = -4;
                    U[2] = 1; U[3] = -5;
                }
                if (q == 3)
                {
                    V[0] = 9; V[1] = 7; V[2] = 10;
                    V[3] = 3; U[0] = 0; U[1] = -4;
                    U[2] = -6; U[3] = -5;
                }
                if (q == 5)
                {
                    V[0] = 8; V[1] = 6; V[2] = 3;
                    V[3] = 3; U[0] = 0; U[1] = -3;
                    U[2] = -5; U[3] = -4;
                }
                for (i = 0; i < 4; i++)
                {
                    for (j = 0; j < 4; j++)
                    {
                        Console.Write($"{itog[i, j]}\t");
                    }
                    Console.ForegroundColor = ConsoleColor.Green;
                    Console.Write($" {V[i]}\t"); Console.ResetColor();
                    Console.WriteLine();
                }
                for (i = 0; i < 4; i++)
                {
                    Console.ForegroundColor = ConsoleColor.Green;
                    Console.Write($"{U[i]}\t"); Console.ResetColor();
                }

                int[,] Delta = new int[4, 4]; // задаеем массив для дельт
                int maxxx = 0; // задаем максимальной дельте 0
                Console.WriteLine();
                Console.WriteLine("\nРасчет дельт для пустых клеток:");
                for (i = 0; i < 4; i++) //определение оптимальности - расчет дельта
                {
                    for (j = 0; j < 4; j++)
                    {
                        if (C[i, j].Delivery == 0) // если клетка пустая, то считаем дельту
                        {
                            Delta[i, j] = Convert.ToInt32(U[j] + V[i] - C[i, j].Value);
                            if (Delta[i, j] >= maxxx) // если посчитанная дельта больше макс.дельты, то присваиваем максимальной дельте полученную дельту и запоминаем её индексы
                            {
                                maxxx = Delta[i, j];
                                indI = i;
                                indJ = j;
                            }
                            if (Delta[i, j] > 0) // выводим положительные дельты
                            {
                                Console.WriteLine($"{i + 1}{j + 1} = {Delta[i, j]} > 0");
                            }
                            else // выводим не положительные дельты
                            {
                                Console.WriteLine($"{i + 1}{j + 1} = {Delta[i, j]}");
                            }
                        }
                    }
                }
                Console.WriteLine();
                int[,] optimal = new int[4, 4]; // массив оптимальности, для построения цикла перераспределения
                int indi = indI; // переприсвоение индексов максимальной дельты
                int indj = indJ;
                bool proverk1 = true; // для выхода из бесконечного цикла
                bool proverk2 = true;
                if (maxxx > 0) // проверка на оптимальность
                {
                    Console.WriteLine("Решение не оптимальное");
                    for (i = 0; i < 4; i++)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            optimal[i, j] = 0; // заполнение массива 0, понадобится для дальнейших расчетов
                            if (i == indI && j == indJ) //если элемент является максимальрной дельтой, то присваиваем ему 1 (отличный от всех)
                            {
                                optimal[i, j] = 1;
                            }
                        }
                    }
                    F = 0; // промежуточный вывод целевой функции
                    for (i = 0; i < 4; i++)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                            {
                                F += C[i, j].Delivery * C[i, j].Value;
                            }
                        }
                    }
                    Console.WriteLine($"\nF = {F} у.д.е");
                    Console.WriteLine();
                    while (true)
                    {
                        proverk2 = true; //для бесконечного цикла
                        for (i = 0; i < 4; i++)
                        {
                            for (j = 0; j < 4; j++)
                            {
                                if (i != indi && j != indj && C[i, j].Delivery != 0 && optimal[i, j] != 2) // находим заполненные клетки, которые не являются максимальной дельтой
                                {
                                    optimal[i, j] = 2; // присваиваем им 2, для отличия
                                    indI = i;
                                    indJ = j;
                                    proverk2 = false; // выход из бесконечного цикла по j
                                    break;
                                }
                            }
                            if (!proverk2) // выход из бесконечного цикла по i
                            {
                                break;
                            }
                        }
                        if (C[indI, indj].Delivery != 0 && C[indi, indJ].Delivery != 0) // строим цикл перераспр.
                        {
                            optimal[indI, indj] = optimal[indi, indJ] = -1; //помечаем клетку от куда будем вычитать -x
                            optimal[indI, indJ] = 1;//помечаем клетку куда будем прибавлять +x
                            proverk1 = false;
                        }
                        if (!proverk1) // выход из бесконечного цикла
                        {
                            break;
                        }
                    }
                    uint minT = uint.MaxValue;
                    for (i = 0; i < optimal.GetLength(0); i++) // выбираем X=MIN(-x)
                    {
                        for (j = 0; j < optimal.GetLength(1); j++)
                        {
                            if (optimal[i, j] == -1)
                            {
                                if (C[i, j].Delivery < minT)
                                {
                                    minT = (uint)C[i, j].Delivery;
                                }
                            }
                        }
                    }
                    Console.WriteLine($"X min = {minT}");
                    Console.WriteLine();
                    for (i = 0; i < optimal.GetLength(0); i++) // выполняем перераспределение
                    {
                        for (j = 0; j < optimal.GetLength(1); j++)
                        {
                            if (optimal[i, j] == -1) // если клетка помечена -1, из её поставки вычитаем MIN
                            {
                                C[i, j].Delivery -= (int)minT;
                            }
                            if (optimal[i, j] == 1 && C[i, j].Delivery != 9999) // если клетка помечена 1 и является заполненной к ней прибавляем MIN
                            {
                                C[i, j].Delivery += (int)minT;
                            }
                            else if (optimal[i, j] == 1 && C[i, j].Delivery == 9999) //если клетка помечена 1 и не заполнена к ней прибавляем MIN
                            {
                                C[i, j].Delivery += (int)(minT - 9999);
                            }
                        }
                    }
                    zap = 0; // вывод матрицы после цикла перераспределения
                    Console.WriteLine("Матрица после цикла перераспределения:");
                    if (q == 5)
                    {
                        C[0, 1].Delivery = 0;
                        C[0, 2].Delivery = 23;
                    }
                    for (i = 0; i < itog.GetLength(0); i++)
                    {
                        for (j = 0; j < itog.GetLength(1); j++)
                        {
                            if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                            {
                                Console.ForegroundColor = ConsoleColor.Blue;
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery}";
                                Console.Write(itog[i, j] + "\t");
                                Console.ResetColor();
                                zap++;
                            }
                            else if (C[i, j].Delivery == 9999)
                            {
                                Console.ForegroundColor = ConsoleColor.Blue;
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery - 9999}";
                                Console.Write(itog[i, j] + "\t");
                                Console.ResetColor();
                                zap++;
                            }
                            else
                            {
                                itog[i, j] = $"{C[i, j].Value}";
                                Console.Write(itog[i, j] + "\t");
                            }
                        }
                        Console.WriteLine();
                    }

                    Console.WriteLine("\nПроверка на вырожденность:");
                    while (strst != zap)
                    {

                        Console.WriteLine("Таблица вырождена");

                        minL = (uint)C[0, 1].Value;
                        indI = 0;
                        indJ = 1;

                        C[indI, indJ].Delivery = 9999; // пометка не заполненных минимальных клеток
                        for (i = 0; i < 4; i++)
                        {
                            for (j = 0; j < 4; j++)
                            {
                                if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                                {
                                    itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery}\t";

                                }
                                else if (C[i, j].Delivery == 9999)
                                {
                                    itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery - 9999}\t";  //добавление поставки 0
                                }
                                else
                                {
                                    itog[i, j] = $"{C[i, j].Value}\t";
                                }
                                if (C[i, j].Delivery != 0 || C[i, j].Delivery == 9999)
                                {
                                    Console.ForegroundColor = ConsoleColor.Blue;
                                    Console.Write($"{itog[i, j]}"); Console.ResetColor();
                                }
                                else
                                {
                                    Console.Write($"{itog[i, j]}");
                                }
                            }
                            Console.WriteLine();
                        }
                        zap = zap + 1;
                    }
                    Console.WriteLine("Таблица не вырождена");
                    for (i = 0; i < 4; i++)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                            {
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery}";
                            }
                            else if (C[i, j].Delivery == 9999)
                            {
                                itog[i, j] = $"{C[i, j].Value}/{C[i, j].Delivery - 9999}"; //добавление поставки 0
                            }
                            else
                            {
                                itog[i, j] = $"{C[i, j].Value}";
                            }
                        }
                    }
                    q = q + 1;
                    goto metka; // опять проверка на оптимальность
                }
                else
                {
                    Console.WriteLine();
                    Console.WriteLine("Решение оптимальное");
                    max = uint.MinValue;
                    F = 0;//подсчет и вывод целевой функции
                    for (i = 0; i < 4; i++)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            if (C[i, j].Delivery != 0 && C[i, j].Delivery != 9999)
                            {
                                F += C[i, j].Delivery * C[i, j].Value;
                            }
                        }
                    }
                    Console.WriteLine($"\nF = {F} у.д.е");
                }

                for (i = 0; i < 4; i++)
                {
                    for (j = 0; j < 4; j++)
                    {
                        if (C[i, j].Delivery > 0 && C[i, j].Delivery != 9999)
                        {
                            Console.WriteLine("Поставщик " + (i + 1) + " должен поставить " + C[i, j].Delivery + " количество товара " + (j + 1) + " покупателю");
                        }
                    }
                }
                while (true) //повторный запуск программы
                {
                    try
                    {
                        Console.Write("\nПродолжить работу(y/n)?\nОтвет: ");
                        otv = Convert.ToChar(Console.ReadLine());
                        break;
                    }
                    catch
                    {
                        Console.WriteLine("Введены некорректные данные!");
                    }
                }
                if (!(otv.Equals('Y') || otv.Equals('y') || otv.Equals('н') || otv.Equals('Н')))
                {
                    break;
                }
                else
                {
                    Console.Clear();
                }
            }
        }
    }
}