// BranchAndBound.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
#include <random>
#include <fstream>
#include <chrono>
#include <string>
using namespace std;
using namespace chrono;
string mainstr = "C:\\Users\\asus\\Desktop\\petya\\Coursework\\Coursework\\graphs\\";
default_random_engine eng(time(0));

using Graph = vector<vector<double>>;
using Way = vector<int>;
using Direction = pair<int, int>;
int N; // количество городов

struct HistoryNode {
    int from;
    int to;
    bool accepted;
    HistoryNode(Direction dir, bool accepted) : from(dir.first), to(dir.second), accepted(accepted) {}
};
using History = vector<HistoryNode>;

struct TreeNode {
    History history;
    Way way;
    int waysCounter;
    double cost;
    bool operator<(const TreeNode& tn) const
    {
        return cost > tn.cost;
    }
    TreeNode() : history(), way(), waysCounter(0), cost(0) {}
    TreeNode(int N, double cost) : history(), way(N, -1), waysCounter(0), cost(cost) {}
};

priority_queue<TreeNode> Nodes;

/*Graph GraphGenerator() {
    Graph graph(N);
    for (int i = 0; i < N; i++) {
        graph[i].resize(N);
    }
    uniform_real_distribution<double> distr(1, 10);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j) {
                graph[i][j] = INFINITY;
                graph[j][i] = INFINITY;
                continue;
            }
            graph[i][j] = distr(eng);
            graph[j][i] = distr(eng);
        }
    }
    return graph;
}*/
//Graph GraphGenerator() {
//  Graph graph;
//  graph.push_back({ INFINITY,20,18,12,8 });
//  graph.push_back({ 5,INFINITY,14,7,11 });
//  graph.push_back({ 12,18,INFINITY,6,11 });
//  graph.push_back({ 11,17,11,INFINITY,12 });
//  graph.push_back({ 5,5,5,5,INFINITY });
//  return graph;
//  }

void ReductionDi(Graph& graph, double& di) {
    double min = INFINITY;
    for (int i = 0; i < N; i++) {
        min = INFINITY;
        for (int j = 0; j < N; j++) {
            if (graph[i][j] < min)
                min = graph[i][j];
        }
        if (min != 0 && min != INFINITY) {
            di += min;
            for (int j = 0; j < N; j++) {
                graph[i][j] -= min;
            }
        }
    }
}

void ReductionDj(Graph& graph, double& dj) {
    double min = INFINITY;
    for (int j = 0; j < N; j++) {
        min = INFINITY;
        for (int i = 0; i < N; i++) {
            if (graph[i][j] < min)
                min = graph[i][j];
        }
        if (min != 0 && min != INFINITY) {
            dj += min;
            for (int i = 0; i < N; i++) {
                graph[i][j] -= min;
            }
        }
    }
}

double Assessment(const Graph& graph, const int i, const int j) {
    double min = INFINITY, sum = 0;
    for (int pj = 0; pj < N; pj++) {
        if (graph[i][pj] < min && pj != j)
            min = graph[i][pj];
    }
    sum += min;
    min = INFINITY;
    for (int pi = 0; pi < N; pi++) {
        if (graph[pi][j] < min && pi != i)
            min = graph[pi][j];
    }
    sum += min;
    return sum;
}
Direction MaxCostForRejection(const Graph& graph, double& maxAssessment) { //выбрали в матрице нулевую клетку с наибольшей стоимостью
    maxAssessment = 0; int maxi, maxj; double assessment; Direction direction;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][j] == 0) {
                assessment = Assessment(graph, i, j);
                if (assessment == INFINITY) {
                    direction.first = i; direction.second = j;
                    maxAssessment = INFINITY;
                    return direction;
                }
                if (assessment > maxAssessment) {
                    maxAssessment = assessment;
                    maxi = i;
                    maxj = j;
                }
            }
        }
    }
    direction.first = maxi; direction.second = maxj;
    return direction;
}

void CrossOut(Graph& graph, const Direction& direction) {
    graph[direction.first][direction.second] = INFINITY;
    graph[direction.second][direction.first] = INFINITY;
    for (int k = 0; k < N; k++) {
        graph[k][direction.second] = INFINITY;
        graph[direction.first][k] = INFINITY;
    }

}
//непонятно делать ли infinity когда не берем
//непонятно нужно ли делать пометку в том, идем ли по этому ребру или нет
//и как ее делать

Graph ConstructGraph(const Graph& graph, const History& history) {
    Graph result = graph;
    for (const auto& historyNode : history) {
        if (historyNode.accepted) {
            CrossOut(result, make_pair(historyNode.from, historyNode.to));
        }
        else {
            result[historyNode.from][historyNode.to] = INFINITY;
        }

        double di = 0, dj = 0;
        ReductionDi(result, di);
        ReductionDj(result, dj);
    }
    return result;
}

void Handle(const TreeNode& node, const Graph& originalGraph) {
    TreeNode yesNode = node, noNode = node;

    double maxAssessment; double di = 0, dj = 0;
    Graph graph = ConstructGraph(originalGraph, node.history);

    Direction zeroMaxAssessment = MaxCostForRejection(graph, maxAssessment);
    CrossOut(graph, zeroMaxAssessment);
    ReductionDi(graph, di);
    ReductionDj(graph, dj);
    yesNode.cost = di + dj + yesNode.cost;
    yesNode.way[zeroMaxAssessment.first] = zeroMaxAssessment.second;
    yesNode.waysCounter++;
    yesNode.history.emplace_back(zeroMaxAssessment, true);
    Nodes.push(yesNode);

    //maxAssessment = Assessment(graph, zeroMaxAssessment.first, zeroMaxAssessment.second);
    noNode.cost = maxAssessment + noNode.cost;
    noNode.history.emplace_back(zeroMaxAssessment, false);
    Nodes.push(noNode);


}

void GraphReader(Graph& graph, int& N, const string strr) {
    ifstream gin(strr);
    gin >> N;
    graph.resize(N);
    for (int i = 0; i < N; i++) {
        graph[i].resize(N);
    }
    double dub;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            gin >> dub;
            if (i == j) dub = INFINITY;
            graph[i][j] = dub;
        }
    }
    gin.close();
}
int main()
{


    ofstream filetime("TSPBAB_time-N.txt");
    ofstream filelongway("TSPBAB_longway-N.txt");
    for (int NUMBER = 40; NUMBER <= 100; NUMBER += 5) {
        double averagelong = 0;
        double averagetime = 0;
        for (int graphforN = 0; graphforN < 20; graphforN++) {
            cout << "N: " << NUMBER << " graph number: " << graphforN << endl;
            double di = 0, dj = 0;
            auto BABstart = high_resolution_clock::now();
            string strr = mainstr + to_string(NUMBER) + "_" + to_string(graphforN) + ".txt";
            Graph graph;
            GraphReader(graph, N, strr);
            ReductionDi(graph, di);
            ReductionDj(graph, dj);
            double lowerBound = di + dj;
            Nodes.emplace(N, lowerBound);

            TreeNode temporaryNode;
            while (!Nodes.empty()) {
                temporaryNode = Nodes.top();
                if (temporaryNode.waysCounter == N)
                    break;
                Nodes.pop();
                Handle(temporaryNode, graph);
            }
            Nodes = priority_queue<TreeNode>();
            /*cout << temporaryNode.cost;
            cout << endl;
            for (int i = 0; i < N; i++) {
                cout << temporaryNode.way[i] << "   ";
            }*/

            auto BABfinish = high_resolution_clock::now();

            averagelong += temporaryNode.cost;
            averagetime += duration_cast<milliseconds>(BABfinish - BABstart).count();
        }
        filelongway << "N: " << NUMBER << " waylong: " << averagelong / 20 << endl;
        filetime << "N: " << NUMBER << " timelong: " << averagetime / 20 << endl;

    }
    filetime.close();
    filelongway.close();
}