С++ стек, очередь, древовидная структура

[lenaiv]

Ломаю голову и не пойму как написать программу вот такого условия: Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

Может кто-нибудь сможет подсказать, может у кого есть идея.

[p51x]

Проблема в чем? Задача несложная то. Идете с корня дерева вниз по наборам и составляете все возможные пути до низу или пустого списка, считаете сумму и находите минимум.

[lenaiv]

Проблема, как это сделать без вектора, применяя списки, очередь и/или стек. И использовать только библиотеку #include <iostream>

[p51x]

А что вы собрались в векторе хранить? Путь? Так его можно хранить в стеке спокойно и потом раскручиать наоборот от низшего чиновника к верху просто доставай элементы.

[lenaiv]

А как это, нам такое не рассказывали.

[p51x]

Что вам не рассказывали? Что такое стек? Что он LIFO?

[lenaiv]

Вот, что про Очередь рассказали

#include <iostream>
using namespace std;


struct Node {

    int elem;
    Node* next;

    Node(int n) // конструктор
    {
        this->elem = n;
        this->next = nullptr;
    }
};

struct FIFO {
    Node* tail, * head;
    FIFO()
    {
        tail = nullptr;
        head = nullptr;
    }

    ~FIFO() // деструктор
    {
        empty();
    }
    void push(int elem) //добавление элемента
    {
        Node* temp = new Node(elem);
        if (is_empty())
        {
            head = tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }

    void pop() //удаление элеиента
    {
        if (is_empty())
        {
            cout << "Очередь пуста!" << endl;
            return;
        }
        Node* temp = head;
        temp = temp->next;
        delete head;
        head = temp;
    }

    void print()// вывод 
    {
        if (head == nullptr) {
            cout << "Очередь пуста!" << endl;
            return;
        }
        else
        {
            Node* temp;
            temp = head;
            while (temp)
            {
                cout << temp->elem << ' ';
                temp = temp->next;
            }
            cout << endl;
        }
    }

    void empty() //очистка
    {
        Node* p = head;
        Node* p2;
        while (p != nullptr)
        {
            p2 = p;
            p = p->next;
            delete p2;
        }
        head = nullptr;
    }

    bool is_empty()
    {
        if (head == nullptr)
            return true;
        else
            return false;
    }
};

А это про Стек

#include <iostream>
using namespace std;


struct Node {

    int elem;
    Node* next;

    Node(int n) // конструктор
    {
        this->elem = n;
        this->next = nullptr;
    }
};

struct Stack {
    Node* head;
    Stack()
    {
        head = nullptr;
    }

    ~Stack() // деструктор
    {
        empty();
    }
    void push(int elem) //добавление элемента
    {
        Node* temp = new Node(elem);
        if (!temp) {
            cout << "Переполнение стека" << endl;
            return;
        }
        temp->elem = elem;
        temp->next = head;
        head = temp;
    }

    void pop() //удаление элеиента
    {
        Node* temp;
        if (head == NULL)
        {
            cout << "Стек пуст!" << endl;
            return;
        }
        else
        {
            temp = head;
            head = head->next;
            free(temp);
        }
    }

    void print()// вывод 
    {
        if (head == nullptr) {
            cout << "Стек пуст!" << endl;
            return;
        }
        else
        {
            Node* temp;
            temp = head;
            while (temp)
            {
                cout << temp->elem << ' ';
                temp = temp->next;
            }
            cout << endl;
        }
    }

    void empty() //очистка
    {
        Node* p = head;
        Node* p2;
        while (p != nullptr)
        {
            p2 = p;
            p = p->next;
            delete p2;
        }
        head = nullptr;
    }
     bool is_empty()
    {
        if (head == nullptr)
            return true;
        else 
            return false;
    }
};

Вот и всё.

[lenaiv]

написала программу, а она не работает (в 40 и 67 ругается на n), не знаю как исправить и правильная она, может кто-нибудь проверит, если знает

#include <iostream>

using namespace std;

// Структура, представляющая чиновника
struct Official {
    int boss; // id начальника
    bool signed_; // подписана ли уже его подпись
    int bribe; // взятка, которую он требует
    // Структура, представляющая визу
    struct Visa {
        bool signed_; // подписана ли уже виза
        int bribe; // взятка, которую требует виза
        Visa* next; // указатель на следующую визу в списке
        Visa(bool signed_, int bribe, Visa* next = nullptr)
            : signed_(signed_), bribe(bribe), next(next) {}
    };
    Visa* visas; // список виз, которые требует чиновник
    Official(int boss = 0, bool signed_ = false, int bribe = 0, Visa* visas = nullptr)
        : boss(boss), signed_(signed_), bribe(bribe), visas(visas) {}
};

// Функция для добавления визы в список виз чиновника
void addVisa(Official& official, bool signed_, int bribe) {
    official.visas = new Official::Visa(signed_, bribe, official.visas);
}

// Функция для удаления списка виз чиновника
void deleteVisas(Official& official) {
    while (official.visas != nullptr) {
        Official::Visa* visa = official.visas;
        official.visas = visa->next;
        delete visa;
    }
}

int main() {
    int n;
    cin >> n; // Считываем количество чиновников
    Official officials[n+1]; // Создаем массив чиновников
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k; // Считываем количество виз, которые требует чиновник
        Official official;
        for (int j = 0; j < k; ++j) {
            int m;
            cin >> m; // Считываем количество виз, которые требует текущая виза
            Official::Visa* visas = nullptr;
            for (int l = 0; l < m; ++l) {
                int visa;
                cin >> visa; // Считываем id чиновников, которые могут подписать визу
                visas = new Official::Visa(false, 0, visas);
            }
            int bribe;
            cin >> bribe; // Считываем взятку, которую требует чиновник за подписание визы
            addVisa(official, false, bribe); // Добавляем визу в список виз чиновника
            deleteVisas(official); // Удаляем список виз, если он был создан ранее
            official.visas = visas; // Присваиваем список виз чиновнику
        }
        officials[i] = official; // Добавляем чиновника в массив чиновников
    }
    for (int i = 1; i <= n; ++i) {
        int boss;
        cin >> boss; // Считываем id начальника чиновника
        officials[i].boss = boss; // Присваиваем начальника чиновнику
    }
    int toSign[n+1]; // Создаем массив для хранения id чиновников, которые нужно подписать
    int top = 0; // Индекс верхнего элемента в массиве toSign
    toSign[top++] = 1; // Добавляем в стек начальника всех чиновников
    int totalBribe = 0; // Общая сумма взяток
    while (top > 0) { // Пока стек не пуст
        int id = toSign[--top]; // Извлекаем из стека верхний элемент
        Official& official = officials[id]; // Получаем ссылку на чиновника
        if (official.signed_) { // Если подпись уже подписана, пропускаем чиновника
            continue;
        }
        bool allVisasSigned = true; // Флаг, указывающий, подписаны ли все визы чиновника
        Official::Visa* visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
        while (visa != nullptr) { // Пока есть визы в списке
            if (!visa->signed_) { // Если виза еще не подписана, выставляем флаг allVisasSigned в false
                allVisasSigned = false;
                break;
            }
            visa = visa->next; // Переходим к следующей визе
        }
        if (allVisasSigned) { // Если все визы подписаны
            official.signed_ = true; // Подписываем подпись чиновника
            totalBribe += official.bribe; // Добавляем взятку к общей сумме
            if (official.boss != 0) { // Если у чиновника есть начальник, добавляем его в стек
                toSign[top++] = official.boss;
            }
        }
        else { // Если не все визы подписаны
            toSign[top++] = id; // Добавляем чиновника в стек
            visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
            while (visa != nullptr) { // Пока есть визы
                if (!visa->signed_) { // Если виза еще не подписана
                    Official& visaOfficial = officials[visa->bribe]; // Получаем ссылку на чиновника, который требует взятку за подписание визы
                    if (visaOfficial.signed_) { // Если чиновник уже подписал подпись
                        visa->signed_ = true; // Подписываем визу
                    }
                    else { // Если чиновник еще не подписал подпись
                        toSign[top++] = visa->bribe; // Добавляем чиновника в стек
                    }
                }
                visa = visa->next; // Переходим к следующей визе
            }
        }
    }
    cout << totalBribe << endl; // Выводим общую сумму взяток
    return 0;
}

[p51x]

Массивы нумеруются с 0. Если у вас есть массив объектов, то не обязательно создавать отдельно еще один и копировать.

Сообщение от lenaiv

а она не работает (в 40 и 67 ругается на n)

VLA это gcc расширения. Создавайте массив динамически или возьмите вектор, который сделает это за вас.

У вас же дерево должно хранить чиновников. Массив зачем?

[lenaiv]

а как тогда, сказали без вектора только, поэтому проблема у меня с этой программой