Code for https://stackoverflow.com/q/77262937/16582

so77262937.cpp

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

// graph theory library https://github.com/JamesBremner/PathFinder
#include "../PathFinder/src/GraphTheory.h"

class cDoor
{
public:
    int capacity; // the number of people that can fit through door
    int connectedKeyholders;
    bool fOpen;

    cDoor()
        : capacity(0),
          connectedKeyholders(0),
          fOpen(false)
    {
    }

    void incCapacity()
    {
        if (capacity < 5)
            capacity++;
    }

    void incKeys()
    {
        connectedKeyholders++;
    }
};

class cPerson
{
public:
    std::string name;
    bool fKey;
    int door;

    cPerson(const std::string &n)
        : name(n),
          fKey(false),
          door(-1)
    {
    }
    void setKey()
    {
        fKey = true;
    }
};

class cInstance
{
public:
    cInstance(
        int keyholderCount,
        bool allDoors = false);

    void generate(int personCount);

    /// @brief Assign keyholders to doors
    void assignKeyHolders();

    void flow();

    void printSetup() const;
    void printFlowModel() const;
    void printPersonDoor(const std::vector<int> &vEdgeFlow) const;

private:
    std::vector<cDoor> vDoor;
    std::vector<cPerson> vPerson;
    raven::graph::sGraphData gd;

    bool fAllDoorsOpen; // true if all doors MUST be opened
    int keyholderCountSpecified;

    void connectperson2door(
        int person,
        int door);

    /// @brief Ensure there are enough keys, if fAllDoors
    void checkKeyCount();

    int keyCount() const;

    std::string personName(int p) const
    {
        return "person" + std::to_string(p);
    }
    std::string doorName(int d) const
    {
        return "door" + std::to_string(d);
    }
    void setEdgeWeight(int ei, int weight);
};

cInstance::cInstance(
    int keyholderCount,
    bool allDoors)
    : keyholderCountSpecified( keyholderCount ),
    fAllDoorsOpen(allDoors)
{
    gd.g.directed();
    gd.g.add("source");
    gd.g.add("sink");
    gd.startName = "source";
    gd.endName = "sink";
}

void cInstance::generate(int personCount)
{
    vDoor.resize(personCount / 5);

    for (int kp = 0; kp < personCount; kp++)
    {
        vPerson.emplace_back(personName(kp));

        int doorCount = 0;
        for (int kd = 0; kd < personCount / 5; kd++)
        {
            // each person can reach random 50% of doors
            if (rand() % 2)
            {
                connectperson2door(kp, kd);
                doorCount++;
            }
        }
        // ensure each person can reach at least one door
        if (!doorCount)
            connectperson2door(kp, 0);
    }

    checkKeyCount();

    printSetup();
}

int cInstance::keyCount() const
{
        return std::count_if(
        vPerson.begin(), vPerson.end(),
        [](const cPerson &p)
        {
            return p.fKey;
        });
}

void cInstance::checkKeyCount()
{
    // assign keys to people
    int kyCount = 0;
    while( kyCount < keyholderCountSpecified ) {
        int kp = rand() % vPerson.size();
        if( vPerson[kp].fKey )
            continue;
        vPerson[kp].setKey();
        kyCount++;
    }

    if (!fAllDoorsOpen)
        return;

    // add keyholders if insufficient specified to open all doors, if perfectly assigned
    int minKey = ceil(vPerson.size() / 2.5);
    while (kyCount < minKey)
    {
        int kd = rand() % vPerson.size();
        if (vPerson[kd].fKey)
            continue;
        vPerson[kd].fKey = true;
        kyCount++;
    }
    for (int kd = 0; kd < vDoor.size(); kd++)
    {
        vDoor[kd].connectedKeyholders = gd.g.adjacentIn(gd.g.find(doorName(kd))).size();
    }
}

void cInstance::connectperson2door(
    int person,
    int door)
{
    int ei = gd.g.add(
        personName(person),
        doorName(door));
    setEdgeWeight(ei, 0);
    vDoor[door].incCapacity();
}

void cInstance::assignKeyHolders()
{
    std::vector<int> vSortedDoor;
    for (int k = 0; k < vDoor.size(); k++)
        vSortedDoor.push_back(k);
    std::sort(
        vSortedDoor.begin(), vSortedDoor.end(),
        [&, this](const int a, const int b)
        {
            if (fAllDoorsOpen)
                return vDoor[a].connectedKeyholders < vDoor[b].connectedKeyholders;

            return vDoor[a].capacity < vDoor[b].capacity;
        });
    for (int door : vSortedDoor)
    {
        if (vDoor[door].fOpen)
            continue;

        int keyCount = 0;
        for (auto &person : vPerson)
        {
            // check for unassigned keyholder
            if (!person.fKey)
                continue;
            if (person.door != -1)
                continue;

            std::cout << "Keyholder " << person.name << " assigned to door " << door << "\n";

            person.door = door;
            keyCount++;
            if (keyCount == 2)
            {
                std::cout << "Door " << door << " opened\n";

                vDoor[door].fOpen = true;
                break;
            }
        }
    }
    if (fAllDoorsOpen)
    {
        for (auto &door : vDoor)
        {
            if (!door.fOpen)
                throw std::runtime_error(
                    "Not all doors are open");
        }
    }
}

void cInstance::flow()
{
    // construct flow model
    for (int kp = 0; kp < vPerson.size(); kp++)
    {
        // check for unassigned keyholder or keyless person
        if (vPerson[kp].fKey && (vPerson[kp].door != -1))
            continue;

        for (int kd = 0; kd < vDoor.size(); kd++)
        {
            // check door is open
            if (!fAllDoorsOpen)
            {
                if (!vDoor[kd].fOpen)
                    continue;
            }

            int ei = gd.g.find(personName(kp), doorName(kd));
            if (ei == -1)
                continue;

            // keyless person can reach open door

            gd.edgeWeight[ei] = 1;
            int esp = gd.g.add(
                "source",
                personName(kp));
            setEdgeWeight(esp, 1);

            // link door to sink
            int eds = gd.g.add(doorName(kd), "sink");
            setEdgeWeight(eds, 3);
        }
    }

    // printFlowModel();

    // calculate flow of keyless people

    std::vector<int> vEdgeFlow;
    double totalFlowKeyless = flows(gd, vEdgeFlow);

    // assigned keyholders
    int assignedKeyHolders = std::count_if(
        vPerson.begin(), vPerson.end(),
        [](const cPerson &p)
        {
            return p.fKey && (p.door != -1);
        });

    std::cout << "Total People who got through " << totalFlowKeyless + assignedKeyHolders
              << " of " << vPerson.size() << "\n";

    printPersonDoor(vEdgeFlow);
}

void cInstance::printPersonDoor(const std::vector<int> &vEdgeFlow) const
{

    for (auto &person : vPerson)
        if (person.fKey && (person.door != -1))
            std::cout << person.name << " through " << doorName(person.door) << "\n";

    for (auto &l : gd.g.edgeList())
    {
        auto namesrc = gd.g.userName(l.first);
        auto namedst = gd.g.userName(l.second);
        if (namesrc.find("person") == -1)
            continue;
        if (namedst.find("door") == -1)
            continue;
        if (vEdgeFlow[gd.g.find(gd.g.userName(l.first), gd.g.userName(l.second))] < 1)
            continue;

        std::cout << namesrc << " through " << namedst << "\n";
    }
}

void cInstance::printSetup() const
{
    std::cout << vPerson.size() << " People, " << vDoor.size() << " Doors\n"
              << keyCount() << " keyholders: ";
    for (auto &person : vPerson)
        if (person.fKey)
            std::cout << person.name << " ";
    std::cout << "\n";
    for (int kd = 0; kd < vDoor.size(); kd++)
    {
        std::cout << "Door " << doorName(kd) << " reachable by ";
        for (int kp = 0; kp < vPerson.size(); kp++)
            if (gd.g.find(personName(kp), doorName(kd)) != -1)
                std::cout << personName(kp) << " ";
        std::cout << "\n";
    }
}

void cInstance::printFlowModel() const
{
    for (auto &l : gd.g.edgeList())
    {
        std::cout << gd.g.userName(l.first)
                  << "->" << gd.g.userName(l.second)
                  << " capacity " << gd.edgeWeight[gd.g.find(l.first, l.second)]
                  << "\n";
    }
}

void cInstance::setEdgeWeight(int ei, int weight)
{
    if (ei >= gd.edgeWeight.size())
        gd.edgeWeight.resize(ei + 1, 0);
    gd.edgeWeight[ei] = weight;
}

main()
{
    cInstance I(12,true);
    I.generate(15);
    I.assignKeyHolders();
    I.flow();
    return 0;
}