MitrofanovaNV_MathModeling_RefPlan/MathModeling/Program.cs

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

namespace MathModeling
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[,] supplyAndDemand = { {16, 26, 12, 24, 3 },
                                      { 5,  2,  19, 27, 2 },
                                      { 29, 23, 25, 16, 8 },
                                      { 2,  25, 14, 15, 21 } };
            int[] consumers = { 14, 14, 14, 14 };
            int[] providers = { 13, 5, 13, 12, 13 };

            if (consumers.Sum() == providers.Sum())
            {
                PhogelMethod(supplyAndDemand, consumers, providers);
                //NorthwestAngleMethod(supplyAndDemand, consumers, providers);
                //DoublePreferenceMethod(supplyAndDemand, consumers, providers);
                //MinElementMethod(supplyAndDemand, consumers, providers);

                PrintTable(supplyAndDemand);
            }
            else
            {
                Console.WriteLine("Некорректные данные!");
            }
            Console.ReadKey();
        }

        private static void MinElementMethod(int[,] supplyAndDemand, int[] consumers, int[] providers)
        {
            bool[,] fill = new bool[supplyAndDemand.GetLength(0), supplyAndDemand.GetLength(1)];
            var minElements = MinElements(supplyAndDemand, fill);
            do
            {
                for (int i = 0; i < minElements.Count; i++)
                {
                    var point = minElements[i];
                    DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, point.Item1, point.Item2);
                }
                minElements = MinElements(supplyAndDemand, fill);
            }
            while (minElements.Count > 0);
        }

        private static void DoStuffOnCoords(int[,] supplyAndDemand, int[] consumers, int[] providers, bool[,] fill, int row, int col)
        {
            int consumer = consumers[row];
            int provider = providers[col];
            var min = Math.Min(consumer, provider);
            if ((consumers[row] -= min) == 0)
            {
                for (int j = 0; j < providers.Length; j++)
                {
                    if (fill[row, j])
                        continue;
                    supplyAndDemand[row, j] = 0;
                    fill[row, j] = true;
                }
            }
            if ((providers[col] -= min) == 0)
            {
                for (int j = 0; j < consumers.Length; j++)
                {
                    if (fill[j, col])
                        continue;
                    supplyAndDemand[j, col] = 0;
                    fill[j, col] = true;
                }
            }
            supplyAndDemand[row, col] = min;
        }

        private static List<(int, int)> MinElements(int[,] table, bool[,] fill)
        {
            int min = int.MaxValue;
            var points = new List<(int, int)>();

            for (int i = 0; i < table.GetLength(0); i++)
            {
                for (int j = 0; j < table.GetLength(1); j++)
                {
                    if (fill[i, j])
                        continue;
                    if (min == table[i, j])
                    {
                        points.Add((i, j));
                    }
                    else if (min > table[i, j])
                    {
                        min = table[i, j];
                        points.Clear();
                        points.Add((i, j));
                    }
                }
            }

            return points;
        }

        private static void PhogelMethod(int[,] supplyAndDemand, int[] consumers, int[] providers)
        {
            bool[,] fill = new bool[supplyAndDemand.GetLength(0), supplyAndDemand.GetLength(1)];
            int[] consumerFees = new int[consumers.Length];
            int[] providerFees = new int[providers.Length];

            while (AnyIsUnfill(fill))
            {
                RecalculateFees(supplyAndDemand, consumerFees, providerFees, fill);

                int rowInd = MaxIndex(consumerFees);
                int colInd = MaxIndex(providerFees);

                if (consumerFees[rowInd] >= providerFees[colInd])
                {
                    int ind = 0;
                    int min = int.MaxValue;
                    for (int i = 0; i < supplyAndDemand.GetLength(1); i++)
                    {
                        if (fill[rowInd, i])
                            continue;
                        if (min > supplyAndDemand[rowInd, i])
                        {
                            ind = i;
                            min = supplyAndDemand[rowInd, i];
                        }
                    }

                    DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, rowInd, ind);
                }
                else
                {
                    int ind = 0;
                    int min = int.MaxValue;
                    for (int i = 0; i < supplyAndDemand.GetLength(0); i++)
                    {
                        if (fill[i, colInd])
                            continue;
                        if (min > supplyAndDemand[i, colInd])
                        {
                            ind = i;
                            min = supplyAndDemand[i, colInd];
                        }
                    }

                    DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, ind, colInd);
                }
            }
        }

        //Перерасчет штрафов
        private static void RecalculateFees(int[,] supplyAndDemand, int[] consumerFees, int[] providerFees, bool[,] fill)
        {
            for (int i = 0; i < consumerFees.Length; i++)
            {
                //Проходится по строкам(потребителям), для каждого создает колонку и создает массив заполненности. 
                int[] row = new int[supplyAndDemand.GetLength(1)];
                bool[] fillMask = new bool[row.Length];
                //Заполняет, копирует строку в массив
                for (int j = 0; j < row.Length; j++)
                {
                    row[j] = supplyAndDemand[i, j];
                    fillMask[j] = fill[i, j];
                }
                //Расчет штрафов
                consumerFees[i] = CalculateFee(row, fillMask);
            }
            // То же самое, что и для потребителей, только для поставщиков 
            for (int i = 0; i < providerFees.Length; i++)
            {
                int[] col = new int[supplyAndDemand.GetLength(0)];
                bool[] fillMask = new bool[col.Length];
                for (int j = 0; j < col.Length; j++)
                {
                    col[j] = supplyAndDemand[j, i];
                    fillMask[j] = fill[j, i];
                }
                providerFees[i] = CalculateFee(col, fillMask);
            }
        }

        private static int CalculateFee(int[] arr, bool[] filled)
        {
            //Находит минимум строки и количество заполненных клеток
            int min = int.MaxValue;
            int filledAmount = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (filled[i])
                {
                    filledAmount++;
                    continue;
                }
                if (arr[i] < min)
                    min = arr[i];
            }
            //Если заполнено все, кроме одной клетки -- штраф == клетка
            if (filledAmount == arr.Length - 1)
                return min;
            //Иначе находим второй
            int min1 = int.MaxValue;
            bool flag = false;
            for (int i = 0; i < arr.Length; i++)
            {
                if (min == arr[i] || filled[i])
                    continue;
                if (arr[i] < min1)
                {
                    min1 = arr[i];
                    flag = true;
                }
            }
            //Если найден второй -- возвращает разницу
            return flag ? min1 - min : 0;
        }

        private static int MaxIndex(int[] arr)
        {
            int max = 0;
            int ind = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] > max)
                {
                    max = arr[i];
                    ind = i;
                }
            }
            return ind;
        }

        //В тупую идет слева-направо, сверху-вниз
        private static void NorthwestAngleMethod(int[,] supplyAndDemand, int[] consumers, int[] providers)
        {
            bool[,] fill = new bool[supplyAndDemand.GetLength(0), supplyAndDemand.GetLength(1)];
            int i = 0;
            for (int j = 0; j < supplyAndDemand.GetLength(0); j++)
            {
                DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, j, i);
                i++;
                DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, j, i);
            }
        }

        //Тот же мин элемент, но больше фигни
        private static void DoublePreferenceMethod(int[,] supplyAndDemand, int[] consumers, int[] providers)
        {
            bool[,] fill = new bool[supplyAndDemand.GetLength(0), supplyAndDemand.GetLength(1)];
            var minElements = DoubleMinElements(supplyAndDemand, fill);
            do
            {
                for (int i = 0; i < minElements.Count; i++)
                {
                    var point = minElements[i];
                    int row = point.Item1;
                    int col = point.Item2;
                    DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, row, col);
                }
                minElements = DoubleMinElements(supplyAndDemand, fill);
            }
            while (minElements.Count > 0);
        }

        //
        private static List<(int, int)> DoubleMinElements(int[,] table, bool[,] fill)
        {
            //Ищет минимальные в строке
            bool[,] isMin = new bool[table.GetLength(0), table.GetLength(1)];
            //по строкам
            for (int i = 0; i < table.GetLength(0); i++)
            {
                int min = int.MaxValue;
                List<int> indices = new List<int>();
                for (int j = 0; j < table.GetLength(1); j++)
                {
                    if (fill[i, j])
                        continue;
                    if (min == table[i, j])
                    {
                        indices.Add(j);
                    }
                    else if (min > table[i, j])
                    {
                        min = table[i, j];
                        indices.Clear();
                        indices.Add(j);
                    }
                }
                indices.ForEach(ind => isMin[i, ind] = true);
            }
            //Список точно минимальных точек, проходит 
            var points = new List<(int, int)>();
            //по столбцам
            for (int j = 0; j < table.GetLength(1); j++)
            {
                int min = int.MaxValue;
                List<int> indices = new List<int>();
                for (int i = 0; i < table.GetLength(0); i++)
                {
                    if (fill[i, j])
                        continue;
                    if (min == table[i, j])
                    {
                        indices.Add(i);
                    }
                    else if (min > table[i, j])
                    {
                        min = table[i, j];
                        indices.Clear();
                        indices.Add(i);
                    }
                }
                //Если есть пересечение -- добавляет в список, затирает. иначе отмечает минимальным
                indices.ForEach(ind =>
                {
                    if (isMin[ind, j])
                    {
                        points.Add((ind, j));
                        isMin[ind, j] = false;
                    }
                    else
                    {
                        isMin[ind, j] = true;
                    }
                });
            }


            //делегат сравнения
            Comparison<(int, int)> comparison = (left, right) =>
            {
                int a = table[left.Item1, left.Item2];
                int b = table[right.Item1, right.Item2];
                return a > b ? 1 : a < b ? -1 : 0;
            };
            //cортирует с начала точки
            points.Sort(comparison);
            int cnt = points.Count;

            //добавляет остальные минимумы
            for (int i = 0; i < table.GetLength(0); i++)
            {
                for (int j = 0; j < table.GetLength(1); j++)
                {
                    if (isMin[i, j])
                    {
                        points.Add((i, j));
                    }
                }
            }
            //сортирует одноминимальные точки (без пересечений)
            points.Sort(cnt, points.Count - cnt, Comparer<(int, int)>.Create(comparison));

            return points;
        }

        private static bool AnyIsUnfill(bool[,] fill)
        {
            for (int i = 0; i < fill.GetLength(0); i++)
            {
                for (int j = 0; j < fill.GetLength(1); j++)
                {
                    if (!fill[i, j])
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        private static void PrintTable(int[,] table)
        {
            for (int i = 0; i < table.GetLength(0); i++)
            {
                for (int j = 0; j < table.GetLength(1); j++)
                {
                    Console.Write(string.Format("{0,-3} ", table[i, j]));
                }
                Console.WriteLine();
            }
        }
    }
}