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

namespace DOLab7
{
    public class Vertex
    {
        public int id;
        public List<Vertex> AdjacentVerticies;
        public List<int> Distances;

        public Vertex()
        {
            AdjacentVerticies = new List<Vertex>();
            Distances = new List<int>();
        }


        public int GetFullWeight()
        {
            int sum = 0;
            for (int i = 0; i < Distances.Count; i++)
            {
                sum += Distances[i];
            }
            return sum;
        }
    }
    public class GomoriXy
    {
        private List<Vertex> verticies = new List<Vertex>();

        private List<Vertex> neighborsCombination;
        public GomoriXy(string path)
        {
            string[] data = File.ReadAllLines(path);
            int peaks = data.Length;

            for (int i = 0; i < peaks; i++)
            {
                verticies.Add(new Vertex());
            }

            for (int i = 0; i < peaks; i++)
            {
                verticies[i].id = i + 1;

                string[] distances = data[i].Split(" ");

                for (int j = 0; j < distances.Length; j++)
                {
                    if (j != i && int.Parse(distances[j]) != 0)
                    {
                        //Додаємо до вершини іншу суміжну вершину
                        verticies[i].AdjacentVerticies.Add(verticies[j]);
                        //Під цим же індексом додаємо відстань до цієї вершини
                        verticies[i].Distances.Add(int.Parse(distances[j]));
                    }
                }
            }
        }
        public void Solve()
        {
            int[,] maximumFlowMatrix = new int[verticies.Count, verticies.Count];

            for (int i = 0; i < verticies.Count; i++)
            {
                for (int j = 0; j < verticies.Count; j++)
                {
                    int min = verticies[i].GetFullWeight(); //Як min спочатку беремо повну вагу(вага дуг, якщо вершину обрізати саму)

                    neighborsCombination = new List<Vertex>();

                    neighborsCombination.Add(verticies[i]);
                    MinCut(neighborsCombination, verticies[j], ref min); //А тут рахуємо чи не буде вага менша, якщо обрізати декілька вершин
                    maximumFlowMatrix[i, j] = min;
                }
            }
            printFinalResults(maximumFlowMatrix);
        }
        public void MinCut(List<Vertex> combination, Vertex current, ref int min)
        {
            //Тут перевіряємо всі можливі комбінації розрізів
            List<Vertex> newCombination = new List<Vertex>(combination);

            for (int i = 0; i < verticies.Count; i++)
            {
                if (newCombination.Contains(verticies[i]) || verticies[i] == current)
                {
                    continue;
                }

                bool isConnected = CheckConnection(verticies[i], newCombination);
                if (isConnected)
                {
                    //якщо до i-тої вершини є шлях з поточного розрізу додаємо її до розрізу
                    newCombination.Add(verticies[i]);
                }
                else
                {
                    continue;
                }

                int currentWeigth = GetWeightOfCut(newCombination);
                if (currentWeigth < min)
                {
                    //Тут знаходимо вагу мінімального розрізу
                    min = GetWeightOfCut(newCombination);
                    neighborsCombination = new List<Vertex>(newCombination);
                }
                //Рекурсивно повторюємо
                MinCut(newCombination, current, ref min);
                //Коли перебрали всі суміжні i-тої вершини, видаляємо її з розрізу
                //Коли переберемо всі можливі комбінації в min буде міститися вага мінімальної,
                //її ми і запишемо в матрицю (maximumFlowMatrix[i, j] = min)
                newCombination.Remove(verticies[i]);
            }
        }
        public bool CheckConnection(Vertex apex, List<Vertex> combination)
        {
            for (int i = 0; i < combination.Count; i++)
            {
                for (int j = 0; j < combination[i].AdjacentVerticies.Count; j++)
                {
                    if (combination[i].AdjacentVerticies[j] == apex)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        public int GetWeightOfCut(List<Vertex> apexes)
        {
            int sum = 0;
            for (int i = 0; i < apexes.Count; i++)
            {
                for (int j = 0; j < apexes[i].AdjacentVerticies.Count; j++)
                {
                    if (!apexes.Contains(apexes[i].AdjacentVerticies[j]))
                    {
                        sum += apexes[i].Distances[j];
                    }
                }
            }
            return sum;
        }
        private void printFinalResults(int[,] matrix)
        {
            Console.WriteLine("Матриця МП-кiв мiж вузлами мережi:\n");

            for (int i = 0; i < verticies.Count; i++)
            {
                for (int j = 0; j < verticies.Count; j++)
                {
                    if (i == j)
                    {
                        Console.Write("-".PadRight(4));
                    }
                    else
                    {
                        Console.Write($"{matrix[i, j]}".PadRight(4));
                    }
                }
                Console.WriteLine();
            }
        }
    }
}