#pragma once
//#include "stdafx.h"
#include <iostream>
#include <typeinfo>
#include <vector>
#include <limits>
#include <list>
#include <iterator>
namespace Project2 {

    using namespace System;
    using namespace System::ComponentModel;
    using namespace System::Collections;
    using namespace System::Windows::Forms;
    using namespace System::Data;
    using namespace System::Drawing;
    using namespace std;

    //Определяем свои типы - пара двух числе будет называться PInt pair int
    typedef pair<int, int> PInt;

    //Вектор чисел будет называться VInt(логично, не правда ли?) vector int
    typedef vector<int> VInt;

    //Вектор интовых векторов будет называться VVInt
    typedef vector<VInt> VVInt;
    //Вектор интовых пар будет называться VPInt
    typedef vector<PInt> VPInt;

    const int inf = numeric_limits<int>::max();

    /*
    * Решает задачу о назначениях Венгерским методом.
    * matrix: прямоугольная матрица из целых чисел (не обязательно положительных).
    *         Высота матрицы должна быть не больше ширины.
    * Возвращает: Список выбранных элементов, по одному из каждой строки матрицы.
    */

    /// <summary>
    /// Summary for MyForm
    /// </summary>
    //Генерация формы - создано автоматически
    public ref class MyForm : public System::Windows::Forms::Form
    {
    public:
        MyForm(void)
        {
            InitializeComponent();
            //
            //TODO: Add the constructor code here
            //
        }

    protected:
        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        ~MyForm()
        {
            if (components)
            {
                delete components;
            }
        }
    private: System::Windows::Forms::DataGridView^  dataGridView1;
    protected:
    private: System::Windows::Forms::Button^  button1;
    private: System::Windows::Forms::NumericUpDown^  Col1;

    private: System::Windows::Forms::NumericUpDown^  Col2;

    private: System::Windows::Forms::Label^  label1;
    private: System::Windows::Forms::Label^  label2;
    private: System::Windows::Forms::TextBox^  resultTextBox;
    private: System::Windows::Forms::TabControl^  tabControl1;
    private: System::Windows::Forms::TabPage^  MainAlghoritm;

    private: System::Windows::Forms::TabPage^  tabPage2;
    private: System::Windows::Forms::TabPage^  tabPage3;
    private: System::Windows::Forms::TextBox^  textBox1;
    private: System::Windows::Forms::TextBox^  textBox2;



    private:
        /// <summary>
        /// Required designer variable.
        /// </summary>
        System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code
        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        void InitializeComponent(void)
        {
            this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());
            this->button1 = (gcnew System::Windows::Forms::Button());
            this->Col1 = (gcnew System::Windows::Forms::NumericUpDown());
            this->Col2 = (gcnew System::Windows::Forms::NumericUpDown());
            this->label1 = (gcnew System::Windows::Forms::Label());
            this->label2 = (gcnew System::Windows::Forms::Label());
            this->resultTextBox = (gcnew System::Windows::Forms::TextBox());
            this->tabControl1 = (gcnew System::Windows::Forms::TabControl());
            this->MainAlghoritm = (gcnew System::Windows::Forms::TabPage());
            this->tabPage2 = (gcnew System::Windows::Forms::TabPage());
            this->tabPage3 = (gcnew System::Windows::Forms::TabPage());
            this->textBox1 = (gcnew System::Windows::Forms::TextBox());
            this->textBox2 = (gcnew System::Windows::Forms::TextBox());
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->dataGridView1))->BeginInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->Col1))->BeginInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->Col2))->BeginInit();
            this->tabControl1->SuspendLayout();
            this->MainAlghoritm->SuspendLayout();
            this->tabPage2->SuspendLayout();
            this->tabPage3->SuspendLayout();
            this->SuspendLayout();
            //
            // dataGridView1
            //
            this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;
            this->dataGridView1->Location = System::Drawing::Point(17, 56);
            this->dataGridView1->Name = L"dataGridView1";
            this->dataGridView1->Size = System::Drawing::Size(549, 319);
            this->dataGridView1->TabIndex = 0;
            //
            // button1
            //
            this->button1->Location = System::Drawing::Point(432, 395);
            this->button1->Name = L"button1";
            this->button1->Size = System::Drawing::Size(134, 23);
            this->button1->TabIndex = 1;
            this->button1->Text = L"Розрахунок";
            this->button1->UseVisualStyleBackColor = true;
            this->button1->Click += gcnew System::EventHandler(this, &MyForm::button1_Click);
            //
            // Col1
            //
            this->Col1->AccessibleName = L"Cols";
            this->Col1->Location = System::Drawing::Point(17, 30);
            this->Col1->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 30, 0, 0, 0 });
            this->Col1->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 2, 0, 0, 0 });
            this->Col1->Name = L"Col1";
            this->Col1->Size = System::Drawing::Size(120, 20);
            this->Col1->TabIndex = 2;
            this->Col1->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) { 2, 0, 0, 0 });
            this->Col1->ValueChanged += gcnew System::EventHandler(this, &MyForm::Col1_ValueChanged);
            //
            // Col2
            //
            this->Col2->AccessibleName = L"Rows";
            this->Col2->Location = System::Drawing::Point(143, 30);
            this->Col2->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 30, 0, 0, 0 });
            this->Col2->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 2, 0, 0, 0 });
            this->Col2->Name = L"Col2";
            this->Col2->Size = System::Drawing::Size(120, 20);
            this->Col2->TabIndex = 3;
            this->Col2->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) { 2, 0, 0, 0 });
            this->Col2->ValueChanged += gcnew System::EventHandler(this, &MyForm::Col1_ValueChanged);
            //
            // label1
            //
            this->label1->AutoSize = true;
            this->label1->Location = System::Drawing::Point(14, 14);
            this->label1->Name = L"label1";
            this->label1->Size = System::Drawing::Size(55, 13);
            this->label1->TabIndex = 4;
            this->label1->Text = L"Стовбець";
            this->label1->Click += gcnew System::EventHandler(this, &MyForm::label1_Click);
            //
            // label2
            //
            this->label2->AutoSize = true;
            this->label2->Location = System::Drawing::Point(140, 14);
            this->label2->Name = L"label2";
            this->label2->Size = System::Drawing::Size(43, 13);
            this->label2->TabIndex = 5;
            this->label2->Text = L"Строка";
            //
            // resultTextBox
            //
            this->resultTextBox->Location = System::Drawing::Point(17, 398);
            this->resultTextBox->Name = L"resultTextBox";
            this->resultTextBox->Size = System::Drawing::Size(409, 20);
            this->resultTextBox->TabIndex = 6;
            //
            // tabControl1
            //
            this->tabControl1->Controls->Add(this->MainAlghoritm);
            this->tabControl1->Controls->Add(this->tabPage2);
            this->tabControl1->Controls->Add(this->tabPage3);
            this->tabControl1->Location = System::Drawing::Point(12, 12);
            this->tabControl1->Name = L"tabControl1";
            this->tabControl1->SelectedIndex = 0;
            this->tabControl1->Size = System::Drawing::Size(599, 460);
            this->tabControl1->TabIndex = 2;
            this->tabControl1->Tag = L"";
            //
            // MainAlghoritm
            //
            this->MainAlghoritm->Controls->Add(this->button1);
            this->MainAlghoritm->Controls->Add(this->label2);
            this->MainAlghoritm->Controls->Add(this->resultTextBox);
            this->MainAlghoritm->Controls->Add(this->label1);
            this->MainAlghoritm->Controls->Add(this->Col2);
            this->MainAlghoritm->Controls->Add(this->dataGridView1);
            this->MainAlghoritm->Controls->Add(this->Col1);
            this->MainAlghoritm->Location = System::Drawing::Point(4, 22);
            this->MainAlghoritm->Name = L"MainAlghoritm";
            this->MainAlghoritm->Padding = System::Windows::Forms::Padding(3);
            this->MainAlghoritm->Size = System::Drawing::Size(591, 434);
            this->MainAlghoritm->TabIndex = 0;
            this->MainAlghoritm->Text = L"Основной алгоритм";
            this->MainAlghoritm->UseVisualStyleBackColor = true;
            //
            // tabPage2
            //
            this->tabPage2->Controls->Add(this->textBox1);
            this->tabPage2->Location = System::Drawing::Point(4, 22);
            this->tabPage2->Name = L"tabPage2";
            this->tabPage2->Padding = System::Windows::Forms::Padding(3);
            this->tabPage2->Size = System::Drawing::Size(591, 434);
            this->tabPage2->TabIndex = 1;
            this->tabPage2->Text = L"Инструкция";
            this->tabPage2->UseVisualStyleBackColor = true;
            this->tabPage2->Click += gcnew System::EventHandler(this, &MyForm::tabPage2_Click);
            //
            // tabPage3
            //
            this->tabPage3->Controls->Add(this->textBox2);
            this->tabPage3->Location = System::Drawing::Point(4, 22);
            this->tabPage3->Name = L"tabPage3";
            this->tabPage3->Padding = System::Windows::Forms::Padding(3);
            this->tabPage3->Size = System::Drawing::Size(591, 434);
            this->tabPage3->TabIndex = 2;
            this->tabPage3->Text = L"О создателях";
            this->tabPage3->UseVisualStyleBackColor = true;
            //
            // textBox1
            //
            this->textBox1->Location = System::Drawing::Point(16, 15);
            this->textBox1->Multiline = true;
            this->textBox1->Name = L"textBox1";
            this->textBox1->ScrollBars = System::Windows::Forms::ScrollBars::Vertical;
            this->textBox1->Size = System::Drawing::Size(556, 398);
            this->textBox1->TabIndex = 0;
            this->textBox1->Text = L"ИНСТРУКЦИЮ ПИСАТЬ СЮДАИНСТРУ\r\nКЦИЮ ПИСАТЬ СЮДАИНСТРУКЦИЮ ПИСАТЬ \r\nСЮДАИНСТРУКЦИЮ "
                L"ПИСАТЬ СЮДАИНСТРУКЦИЮ \r\nПИСАТЬ СЮДАИНСТРУКЦИЮ ПИСАТЬ СЮДАИНСТРУКЦИЮ \r\nПИСАТЬ \r\nС"
                L"ЮДА";
            //
            // textBox2
            //
            this->textBox2->Location = System::Drawing::Point(18, 15);
            this->textBox2->Multiline = true;
            this->textBox2->Name = L"textBox2";
            this->textBox2->ScrollBars = System::Windows::Forms::ScrollBars::Vertical;
            this->textBox2->Size = System::Drawing::Size(556, 398);
            this->textBox2->TabIndex = 1;
            this->textBox2->Text = L"ВОТ СЮДА НАПИШИ О СЕБЕ";
            this->textBox2->TextChanged += gcnew System::EventHandler(this, &MyForm::textBox2_TextChanged);
            //
            // MyForm
            //
            this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
            this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
            this->ClientSize = System::Drawing::Size(623, 489);
            this->Controls->Add(this->tabControl1);
            this->Name = L"MyForm";
            this->Text = L"Венгерский алгоритм\\Задача о назначениях";
            this->Load += gcnew System::EventHandler(this, &MyForm::MyForm_Load);
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->dataGridView1))->EndInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->Col1))->EndInit();
            (cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->Col2))->EndInit();
            this->tabControl1->ResumeLayout(false);
            this->MainAlghoritm->ResumeLayout(false);
            this->MainAlghoritm->PerformLayout();
            this->tabPage2->ResumeLayout(false);
            this->tabPage2->PerformLayout();
            this->tabPage3->ResumeLayout(false);
            this->tabPage3->PerformLayout();
            this->ResumeLayout(false);

        }
#pragma endregion
    private: System::Void MyForm_Load(System::Object^  sender, System::EventArgs^  e) {
    }
    private: System::Void label1_Click(System::Object^  sender, System::EventArgs^  e) {
    }

//Тут заканчивается автоматическая генерация формы конструктором

    //Основной алгоритм, производящий вычисления удачных пар по венгерскому алгоритму
    private: VPInt hungarian(const VVInt &matrix){

                 // Размеры матрицы
                 int height = matrix.size(), width = matrix[0].size();

                 // Значения, вычитаемые из строк (u) и столбцов (v)
                 VInt u(height, 0), v(width, 0);

                 // Индекс помеченной клетки в каждом столбце
                 VInt markIndices(width, -1);

                 // Будем добавлять строки матрицы одну за другой
                 for (int i = 0; i < height; i++) {
                     VInt links(width, -1);
                     VInt mins(width, inf);
                     VInt visited(width, 0);

                     // Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)
                     int markedI = i, markedJ = -1, j;
                     while (markedI != -1) {
                         // Обновим информацию о минимумах в посещенных строках непосещенных столбцов
                         // Заодно поместим в j индекс непосещенного столбца с самым маленьким из них
                         j = -1;
                         for (int j1 = 0; j1 < width; j1++)
                         if (!visited[j1]) {
                             if (matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) {
                                 mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
                                 links[j1] = markedJ;
                             }
                             if (j == -1 || mins[j1] < mins[j]){}
                             j = j1;
                         }

                         // Теперь нас интересует элемент с индексами (markIndices[links[j]], j)
                         // Произведем манипуляции со строками и столбцами так, чтобы он обнулился
                         int delta = mins[j];
                         for (int j1 = 0; j1 < width; j1++)
                         if (visited[j1]) {
                             u[markIndices[j1]] += delta;
                             v[j1] -= delta;
                         }
                         else {
                             mins[j1] -= delta;
                         }
                         u[i] += delta;

                         // Если коллизия не разрешена - перейдем к следующей итерации
                         visited[j] = 1;
                         markedJ = j;
                         markedI = markIndices[j];
                     }

                     // Пройдем по найденной чередующейся цепочке клеток, снимем отметки с
                     // отмеченных клеток и поставим отметки на неотмеченные
                     for (; links[j] != -1; j = links[j])
                         markIndices[j] = markIndices[links[j]];
                     markIndices[j] = i;
                 }

                 // Вернем результат в естественной форме
                 VPInt result;
                 for (int j = 0; j < width; j++)
                 if (markIndices[j] != -1)
                     result.push_back(PInt(markIndices[j], j));
                 return result;
    }

    //Обработчик нажатия на кнопку
    private: System::Void button1_Click(System::Object^  sender, System::EventArgs^  e) {
                 //Получаем размеры таблицы
                 int sizeCols = Convert::ToInt32(Col1->Value);
                 int sizeRows = Convert::ToInt32(Col2->Value);

                 //Проверяем что количество столбцов и колонок соответствует условиям задачи
                 if (sizeRows > sizeCols)
                 {
                     //Если не соответствует выводим сообщение на экран и заканчиваем выполнение
                     MessageBox::Show(this, "Number of cols must be greater or equals than number of rows", "My Application", MessageBoxButtons::OK, MessageBoxIcon::Asterisk);
                     return;
                 }

                 //Если дошли до сюда, значит по размерам матрицы все правильно
                 //Создаем временный вектор в который будем аккумулировать данные из строк матрицы
                 vector <int> tempVector;
                 //Свой собственный переопределенный тип, представляющий собой вектор векторов
                 VVInt solvingMatrix(0);

                 //Помещаем значения из таблицы во временный вектор
                 for (int i = 0; i < sizeCols; i++){
                     vector <int> tempVector;
                     for (int j = 0; j < sizeRows; j++){
                         //Помещаем тут из таблицы dataGridView1 колонки Rows[i] ячейки Cells[j] значение Value
                         tempVector.insert(tempVector.end(), Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value));
                     }
                     //Передаем временный вектор внутрь матрицы, ставим его на позицию последнего в векторе - то есть он становится последним
                     //Метод добавления принимает в себя два значения - куда вставлять и что вставлять, после того как строка набита в вектор,
                     //Добавляем строку в вектор векторов VVInt
                     solvingMatrix.insert(solvingMatrix.end(), tempVector);


                     //Решаем нашу матрицу при помощи Венгерского алгоритма
                     VPInt result = hungarian(solvingMatrix);


                     //Выводим пары строка-столбец, которые решают нашу задачу
                     for (int i = 0; i < result.size(); i++) {
                         resultTextBox->Text += Convert::ToString(result[i].first + 1) + "-";
                         resultTextBox->Text += Convert::ToString(result[i].second + 1) + "  ";
                     }

                 }
    }

             //Обработчик события - изменение значения переключаемых полей ввода размеров матрицы
    private: System::Void Col1_ValueChanged(System::Object^  sender, System::EventArgs^  e) {
                 //Получаем данные о размерах матрицы
                 int sizeCols = Convert::ToInt32(Col1->Value);
                 int sizeRows = Convert::ToInt32(Col2->Value);

                 //Создаем таблицу заданного размера
                 dataGridView1->ColumnCount = sizeCols;
                 dataGridView1->RowCount = sizeRows;

                 //Заполняем нулями ячейки если в них еще ничего не записано, если записано то не перезаполняем
                 for (int i = 0; i < sizeCols; i++){
                     for (int j = 0; j < sizeRows; j++){
                         dataGridView1->Columns[i]->HeaderCell->Value = Convert::ToString(i + 1);
                         dataGridView1->Rows[j]->HeaderCell->Value = Convert::ToString(j + 1);
                         if (dataGridView1->Rows[j]->Cells[i]->Value == 0){
                             dataGridView1->Rows[j]->Cells[i]->Value = 0;
                         }
                     }
                 }

                 //Настраиваем отображение
                 dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);
                 dataGridView1->AutoResizeColumns();
    }
    private: System::Void tabPage2_Click(System::Object^  sender, System::EventArgs^  e) {
    }
private: System::Void textBox2_TextChanged(System::Object^  sender, System::EventArgs^  e) {
}
};
}