C++ Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

[lenaiv]

Мне нужно было написать программу на С++ по условию (дополнительно разъяснению к условию) с применением на стек, очередь, двунаправленные и кольцевой списки. Я написала, но мне говорят, что вывод программы верный, а списки нужно было расписывать вручную, а не автоматом. Может кто подскажет как это сделать. Мне дали дополнение (я прикрепила в файлах), по которому можно вручную расписать, но у меня не получается.

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

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

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

Моя программа

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

// предварительное объявление узла графа, для установления связей 
struct Node;
using visas_spisok_t = vector<Node*>; // тип : список виз
// набор виз и цена набора
struct VisaPack
{
    visas_spisok_t vspisok;
    int cena; // цена
};

using visas_pack_spisok_t = vector<VisaPack>; // тип : список наборов виз
using chinovniki_t = vector<Node*>; // тип : список чиновников
struct Chinovnik
{
    int pn; // PN - индекс чиновника, нужен для к запоминанию n значений
    visas_pack_spisok_t vpspisok; // список наборов виз
};
struct Node
{
    Chinovnik* chinovnik{};    // указатель на чиновника
    chinovniki_t pod_chinovniki{}; // список подчиненных
};

// стурктура дл¤ сохранения наименьшей суммы и соответствующего набора виз
struct Memo
{
    int sum{ -1 }; // -1 - не требует взятки
    int vpspiski{ -1 }; // индекс набора виз, -1 - нет список наборов виз пуст
};

// граф
class Graf
{
public:
    // chinovnik - начальник всех начальников, n - количество чиновников
    Graf(Node* chinovnik, const vector<Chinovnik>& chinovniki, int n) : head{ chinovnik }, chinovniki{ chinovniki }, mem(n) {  }
    void print()
    {
        if (head)
            print(head);
    }
    int Min_Sum_and_Print()
    {
        if (head)
        {
            int min_sum = poluchit_min_contract(head);

            // стек PN всех чиновников поставивших подписи, начиная с самых нижних уровней
            stack<queue<int>> sq;
            queue<int> pod_chinovniki;
            // добавили главного чиновника
            pod_chinovniki.push(head->chinovnik->pn);
            do
            {
                sq.push({}); // добавили пустую очередь
                int n = pod_chinovniki.size();
                for (int i = 0; i != n; ++i)
                {
                    auto chinovnik_pn = pod_chinovniki.front();
                    pod_chinovniki.pop();
                    sq.top().push(chinovnik_pn);
                    if (mem[chinovnik_pn].vpspiski != -1)
                    {
                        auto& chinovnik_vspisok = (chinovniki[chinovnik_pn].vpspisok[mem[chinovnik_pn].vpspiski]).vspisok;
                        int end = chinovnik_vspisok.size();
                        for (int k = 0; k != end; ++k)
                            pod_chinovniki.push(chinovnik_vspisok[k]->chinovnik->pn);
                    }
                }
            } while (!pod_chinovniki.empty());

            // печать чиновников подписей
            cout << "порядок получения подписей для лицензии, числа - ID чиновников " << endl;
            while (!sq.empty())
            {
                auto& q = sq.top();
                while (!q.empty())
                {
                    cout << q.front() << ' ';
                    q.pop();
                }
                cout << endl;
                sq.pop();
            }
            return min_sum;
        }
        return -1; // останавливает выполнение программы, если неверно, то будет -1
    }
private:
    Node* head; // корень графа
    // массив промежуточных результатов для каждого обработанного чиновника
    vector<Memo> mem;
    const vector<Chinovnik>& chinovniki;

    void print(const Node* h, int level = 0)
    {
        for (int i = 0; i < level; i++)
            cout << "    ";
        cout << " ID чиновника " << h->chinovnik->pn << endl;
        for (int i = 0; i < h->pod_chinovniki.size(); i++)
            print(h->pod_chinovniki[i], level + 1);
    }

    int poluchit_min_contract(Node* h)
    {
        if (mem[h->chinovnik->pn].sum == -1)
        {
            vector<int> cena_s;
            for (auto& contract : h->chinovnik->vpspisok)
            {
                int total_cena = contract.cena;
                for (auto& chinovnik : contract.vspisok)
                    total_cena += poluchit_min_contract(chinovnik);
                cena_s.push_back(total_cena);
            }
            auto min_cena_it = min_element(cena_s.begin(), cena_s.end());
            mem[h->chinovnik->pn].sum = (min_cena_it == cena_s.end() ? 0 : *min_cena_it);
            mem[h->chinovnik->pn].vpspiski = (min_cena_it == cena_s.end() ? -1 : (min_cena_it - cena_s.begin()));
        }
        return mem[h->chinovnik->pn].sum;
    }
};

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

    int n;
    cout << " Введите количество чиновников ";
    cin >> n;
    vector<Chinovnik> chinovniki(n);
    vector<Node> node_s(n);

    for (int in = 0; in != n; ++in)
    {
        int pn, k, v;
        cout << " Введите через пробел: ID (порядковый номер) чиновника, количество подчиненных текущего чиновника, количество наборов виз (для текущего чиновника) ";
        cin >> pn >> k >> v;
        chinovniki[pn].pn = pn;
        chinovniki[pn].vpspisok.resize(v);
        node_s[pn].chinovnik = &chinovniki[pn];
        node_s[pn].pod_chinovniki.resize(k);
        for (int ik = 0; ik != k; ++ik)
        {
            int kpn;
            cout << " Введите ID (порядковый номер) подчиненных ";
            cin >> kpn;
            node_s[pn].pod_chinovniki[ik] = &node_s[kpn];
        }

        for (int iv = 0; iv != v; ++iv)
        {
            int vn;
            cout << " Введите количество виз " << iv+1 << " набора ";
            cin >> vn;
            chinovniki[pn].vpspisok[iv].vspisok.resize(vn);
            for (int ivn = 0; ivn != vn; ++ivn)
            {
                int ivpn;
                cout << " Введите визы, ID подчиненных подписи которых необходимы ";
                cin >> ivpn;
                chinovniki[pn].vpspisok[iv].vspisok[ivn] = &node_s[ivpn];
            }
            cout << " Введите цену " << iv+1 << " набора виз ";
            cin >> chinovniki[pn].vpspisok[iv].cena;
        }
    }
    Graf graf(&node_s[0], chinovniki, n);
    graf.print();
    int min_sum = graf.Min_Sum_and_Print();
    cout << " Стоимость: " << min_sum << endl;
    system("pause");
    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;
}