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);
                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];
                    int row = point.Item1;
                    int col = point.Item2;
                    DoStuffOnCoords(supplyAndDemand, consumers, providers, fill, row, col);
                }
                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 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();
            }
        }
    }
}