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

[p51x]

Ну так наконец-то прочитайте про деревья и работу с ними

[lenaiv]

а так тоже неправильно

#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 = new Official[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, visa, 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 = new int[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; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную под массив

return 0;
}

[lenaiv]

вот так правильно или нет

#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 = new Official[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, visa, 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 = new int[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; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную под динамический массив чиновников
    delete[] toSign; // Освобождаем память, выделенную под динамический массив id чиновников, которые нужно подписать
    return 0;
}

[p51x]

Еще раз: массивы нумеруются с 0. Нет дерева. Вы в цикле перезаписываете visas вместо их накопления. bribe у вас должен быть не ид чиновника, который требует взятку, а сумма взятки для этого чиновника. У чиновника может быть несколько наборов "виз", т.е. несколько путей и вам по задаче надо найти минимум.
Т.е. задача не решена.

[lenaiv]

исправила, но не работает

#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() 
{
    setlocale(LC_ALL, "Russian");
    int n;
    cout << "Введите количество чиновников";
    cin >> n; // Считываем количество чиновников
    Official* officials = new Official[n + 1]; // Создаем динамический массив чиновников
    for (int i = 1; i <= n; ++i)
    {
        int k;
        cout << "Введите количество виз, которые требует чиновник";
        cin >> k; // Считываем количество виз, которые требует чиновник
        Official official;
        for (int j = 0; j < k; ++j)
        {
            int m;
            cout << "Введите количество виз, которые требует текущая виза";
            cin >> m; // Считываем количество виз, которые требует текущая виза
            Official::Visa* visas = nullptr;
            for (int l = 0; l < m; ++l) 
            {
                int visa;
                cout << "Введите id чиновников, которые могут подписать визу";
                cin >> visa; // Считываем id чиновников, которые могут подписать визу 
                visas = new Official::Visa(false, visa, visas);
            }
            int bribe;
            cout << "Введите взятку, которую требует чиновник за подписание визы";
            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 = new int[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; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную под динамический массив чиновников
    delete[] toSign; // Освобождаем память, выделенную под динамический массив id чиновников, которые нужно подписать
    return 0;
}

[p51x]

а что исправили то?

[lenaiv]

Посмотрите, пожалуйста, я написала программу, а она почему, то первую сумму не хочет прибавлять и порядок выдает не верный. Может кто-то подскажет.

#include <iostream>
#include <vector>

using namespace std;

// Определение структуры для представления элемента стека
struct node {
    int elem;          
    node* next;       
    node(int n) {      
        this->elem = n;
        this->next = nullptr;
    }
};

 
struct Stek {
    node* head;        
    Stek() {            
        head = nullptr;
    }
    ~Stek() {           
        ochistka();
    }

    
    void dobav_el(int elem) {
        node* temp = new node(elem);  
        if (!temp) {
            cout << "Стек переполнен" << endl; 
            return;
        }
        temp->elem = elem;      
        temp->next = head;      
        head = temp;            
    }

    
    void delet_el() {
        node* temp;
        if (head == nullptr) {
            cout << "Стек пустой" << endl; // Если стек пуст, выводим сообщение
            return;
        }
        else {
            temp = head;        
            head = head->next;  
            delete temp;        
        }
    }

     
    void vivod() {
        if (head == nullptr) {
            cout << "Стек пустой" << endl; // Если стек пуст, выводим сообщение
            return;
        }
        else {
            node* temp;
            temp = head;
            while (temp) {
                cout << temp->elem << ' ';  
                temp = temp->next;
            }
            cout << endl;
        }
    }

   
    void ochistka() {
        node* t1 = head;
        node* t2;
        while (t1 != nullptr) {
            t2 = t1;
            t1 = t1->next;
            delete t2; // Удаляем элементы стека
        }
        head = nullptr; // Указываем, что стек пуст
    }

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

 
struct Official {
    int boss;         
    bool signed_;    
    int cena;         
    struct Visa {
        bool signed_;  
        int cena;      
        Visa* next;    
        Visa(bool signed_, int cena, Visa* next = nullptr) : signed_(signed_), cena(cena), next(next) {}
    };
    Visa* visas;       
    Official(int boss = 0, bool signed_ = false, int cena = 0, Visa* visas = nullptr) : boss(boss), signed_(signed_), cena(cena), visas(visas) {}
};

 
struct SignatureOrder {
    int officialId;    
    SignatureOrder* next;  
    SignatureOrder(int officialId, SignatureOrder* next = nullptr) : officialId(officialId), next(next) {}
};

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

 
void deleteVisas(Official& official) {
    while (official.visas != nullptr) {
        Official::Visa* visa = official.visas;
        official.visas = visa->next;
        delete visa;  
    }
}

int main() {
    setlocale(LC_ALL, "Russian");  

    int n;
    cout << "Введите количество чиновников: ";
    cin >> n; 

    Official* officials = new Official[n + 1]; // Создаем массив структур Official для представления чиновников

    SignatureOrder* signatureOrder = nullptr;  

    
    for (int i = 1; i <= n; ++i) {
        int k;
        cout << "Введите количество виз, которые требует чиновник " << i << ": ";
        cin >> k;  

        Official official;  

        for (int j = 0; j < k; ++j) {
            int m;
            cout << "Введите количество виз, которые требует текущая виза: ";
            cin >> m;  

            Official::Visa* visas = nullptr;  
            int visaCost = 0;  

            for (int l = 0; l < m; ++l) {
                int visa;
                cout << "Введите id чиновников, которые могут подписать визу: ";
                cin >> visa;  

                visas = new Official::Visa(false, visa, visas); // Создаем новую визу и добавляем ее в список виз
                visaCost += officials[visa].cena; // Увеличиваем сумму взяток на сумму взятки за текущую визу
            }

            int cena;
            cout << "Введите взятку, которую требует чиновник за подписание визы: ";
            cin >> cena; // Запрашиваем сумму взятки, которую требует чиновник за подписание визы и считываем в переменную cena

            addVisa(official, false, cena); // Добавляем информацию о визах к текущему чиновнику
            deleteVisas(official); 
            official.visas = visas;  
            official.cena = cena + visaCost;  

           
            signatureOrder = new SignatureOrder(i, signatureOrder);
        }

        officials[i] = official;  
    }

    
    for (int i = 1; i <= n; ++i) {
        int boss;
        cout << "Введите id начальника чиновника " << i << ": ";
        cin >> boss; // Запрашиваем id начальника текущего чиновника и считываем в переменную boss

        officials[i].boss = boss; // Устанавливаем начальника для текущего чиновника
    }

    Stek stack;  
    stack.dobav_el(1);  
    int totalcena = 0;  

    
    while (!stack.eto_ochistka()) {
        int id = stack.head->elem; // Получаем id текущего чиновника из вершины стека
        Official& official = officials[id]; // Получаем ссылку на структуру текущего чиновника
        stack.delet_el(); // Удаляем текущего чиновника из стека

        if (official.signed_) {  
            continue; 
        }

        bool allVisasSigned = true; // Флаг, обозначающий, что все визы для текущего чиновника подписаны
        Official::Visa* visa = official.visas; // Получаем указатель на первую визу текущего чиновника

        while (visa != nullptr) {
            if (!visa->signed_) { // Если виза не подписана
                allVisasSigned = false; // Устанавливаем флаг в false
                break; // Выходим из цикла
            }
            visa = visa->next; 
        }

        if (allVisasSigned) { // Если все визы для текущего чиновника подписаны
            official.signed_ = true; // Устанавливаем флаг подписи для текущего чиновника
            totalcena += official.cena; // Увеличиваем общую сумму взяток на сумму взяток текущего чиновника
            if (official.boss != 0) {
                stack.dobav_el(official.boss); // Если есть начальник, добавляем его id в стек
            }
        }
        else {
            stack.dobav_el(id); // Если не все визы подписаны, добавляем текущего чиновника в стек
            visa = official.visas; // Снова получаем указатель на первую визу текущего чиновника

            while (visa != nullptr) {
                if (!visa->signed_) { // Если виза не подписана
                    Official& visaOfficial = officials[visa->cena]; // Получаем ссылку на чиновника, требующегося для визы
                    if (visaOfficial.signed_) {
                        visa->signed_ = true; // Если этот чиновник уже подписался, подписываем визу
                    }
                    else {
                        stack.dobav_el(visa->cena); // Если не подписался, добавляем его id в стек
                    }
                }
                visa = visa->next; // Переходим к следующей визе
            }
        }
    }

    // Выводим порядок получения подписей
    cout << "Порядок получения подписей для лицензии: ";
    SignatureOrder* current = signatureOrder;
    while (current != nullptr) {
        cout << current->officialId << " ";
        current = current->next;
    }
    cout << endl;

    cout << "Общая сумма взяток: " << totalcena << endl; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную для массива чиновников
    return 0;
}