Минимальное расстояние от листа до корня дерева

Ответ 1

Эта проблема может быть решена путем нахождения кратчайшего пути из каждой записи node (слева) до выхода node (root).

В моей реализации ниже я использовал матрицу смежности для представления такого (направленного) графа, но вы можете думать о ней как о бинарном дереве (потому что проблема определила максимум 2 очереди ввода для каждого перехода).

Псевдо-код

int shortestPath(root)
    if (both childs exists)
        return min(shortestPath(node->left),shortestPath(node->right))*2+1
    if (left child exists)
        return shortestPath(node->left)
    if (right child exists)
        return shortestPath(node->right)
    return 0; //no childs

Единственное различие между нормальным кратчайшим путем и этой проблемой состоит в том, что всякий раз, когда у нас есть два входящих очереди, полицейский отправляет поклонников из каждой очереди поочередно. Это означает, что для прохождения этой очереди потребуется удвоить время +1. +1 - это потому, что мы предполагаем, что он начинается с более длинного пути очереди.

Код С++

Вот рабочий код на С++, который возвращает пару с оптимальным временем и его контуром. Если существует более одного оптимального пути, он возвращает только один из них.

const pair<int,vector<int>>& min(const pair<int,vector<int>>& a, const pair<int,vector<int>>& b) {
  return (a.first < b.first) ? a : b;
}

pair<int,vector<int>> findShortestPath(vector<vector<int>>& graph, int v){
    vector<pair<int,vector<int>>> childs;
    for (int i=0; i<v; i++){
        if (graph[i][v] != -1){
            pair<int,vector<int>> path = findShortestPath(graph,i);
            path.second.push_back(v+1);
            childs.push_back(make_pair(path.first + graph[i][v], path.second));
        }
    }
    if (childs.size() == 2){
        pair<int,vector<int>> path = min(childs[0],childs[1]);
        return make_pair(path.first*2+1, path.second);
    }
    if (childs.size() == 1){
        return make_pair(childs[0].first,childs[0].second);
    }
    else{
        vector<int> start = {v+1};
        return make_pair(0,start);
    }
}

временная сложность этого кода O(n^2), где n - количество вершин. Вы также можете реализовать его в O(n), используя представление списка смежности (= двоичное дерево).

Для полноты здесь также есть main для создания графика из данного ввода и печати оптимального времени и пути. Посмотрите это живое испытание вашего примера ввода

int main()
{
    int n, e;
    cin >> n; //num of vertices
    cin >> e; //num of queues
    vector<vector<int>> graph;

    //initialize graph matrix cells to -1
    graph.resize(n);
    for (int i=0;i<n;i++){
        graph[i].resize(n);
        for (int j=0;j<n;j++)
            graph[i][j] = -1;
    }

    //add edges and their weights
    for (int i=0;i<e;i++){
        int s,d,val;
        cin >> s >> d >> val;
        graph[s-1][d-1] = val;
    }

    //run algorithm
    pair<int,vector<int>> path = findShortestPath(graph, n-1);

    //print results
    cout << path.first << endl;
    for (int i=0;i<path.second.size()-1;i++)
        cout << path.second[i] << " -> ";
    cout << path.second[path.second.size()-1] << endl;

    return 0;
}

Ответ 2

Это должно решаться динамическим программированием.
Пусть P (j) - позиция человека, если он принимает оптимальный веер, чтобы пройти через точку соединения j. Например, P (6) = 4 в вашем случае, потому что кто-то, прибывающий в точку соединения 3, будет четвертым, чтобы пройти через точку соединения 6 (после P27, P26 и P28).
Следующие три утверждения очевидны и решают проблему.
Если "точка соединения" j является вентилятором, P (j) = 1 (базовый случай)
Если "точка соединения" j является правильной точкой соединения с дочерними l и r, и в очереди между l и j и y люди находятся в очереди между r и j, мы имеем P (j) = 2 * min (P (l) + x, P (r) + y)
Если кто-то, если n'th пройти через счетчик, требуется n-1 раз, чтобы туда добраться.
Вы можете легко найти время с помощью DP и с помощью некоторых книг (если минимум достигнут слева или справа), вы можете получить оптимальный вентилятор.