bhabha

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

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
#include <random>
#include <fstream>
using namespace std;
//default_random_engine eng(time(0));

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

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;
                    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) {
    ifstream gin("D:\\code\\С++\\GRAPHCREATOR\\graph.txt");
    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()
{
    /*Graph graph(N);*/ double di = 0, dj = 0;
    Graph graph;
    /*graph = GraphGenerator();*/
    GraphReader(graph, N);
    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);
    }
    cout << temporaryNode.cost;
    cout << endl;
    for (int i = 0; i < N; i++) {
        cout << temporaryNode.way[i] << "   ";
    }






}