0

Имеется транспортная сеть, включающая мосты. При превышении грузоподъемности некоторого моста он разрушается. Определить максимальный вес груза, который может быть транспортирован из пункта А в пункт В без превышения грузоподъемности находящихся на маршруте движения транспорта мостов.

Я нахожу в графе все пути из А в В и вывожу максимальную грузоподъёмность на данном маршруте. Вот функция для этого:

void FindPath(int Vertex) { // Поиск всех путей в графе
    if (maxWeight > WeightLimit[Vertex]) {
        lastMaxWeight = maxWeight;
        maxWeight = WeightLimit[Vertex];
    }
    CurrentPath[j] = Vertex; // добавление в путь текущей вершины 
    map.arr[map.mapCount++] = Vertex;  // коррекция множества вершин пути 
    j++;
    if (Vertex == pointB - 1) {
        cout << endl << "Найден путь: ";
        for (int i = 0; i < j; i++) // вывод пути           
            cout << CurrentPath[i] + 1 << " ";
        cout << endl << "Его максимальная грузоподъёмность: " << maxWeight << endl;
    }
    else {
        for (int i = 0; i < VertexCount; i++)
            if (!isInMap(i) && matrix[Vertex][i]) // поиск в глубину: выбор продолжения пути без цикла 
                FindPath(i);
    }

    // здесь оказываемся после нахождения очередного пути или в случае попадания в тупик 
    maxWeight = lastMaxWeight;
    map.mapCount--; // исключение из множества вершин пути последней вершины  
    j--;    // возврат в предыдущую вершину 
}

Пути находит правильно, но грузоподъёмность выводит неверную. Например для пути 1-4-5 выводит максимальную грузоподъёмность 27, но на самом деле она 22 (4 мост имеет минимальную грузоподъёмность)

Вот полный код программы, подскажите, что нужно исправить, чтобы выводило корректную максимальную грузоподъёмность?

#include <iostream>
#include <iomanip>
using std::cout;
using std::cin;
using std::endl;
using std::setw;

#define BridgeCount 10

int matrix[BridgeCount][BridgeCount];  // матрица смежности 
int WeightLimit[BridgeCount];
int VertexCount;   // количество пунктов 
int CurrentPath[BridgeCount]; // текущий путь 
int pointA, pointB, j;
int maxWeight = 0;
int lastMaxWeight = 0;

struct set {
    int arr[BridgeCount];
    int mapCount;
} map; // множество вершин, входящих в путь 


void InputMatrix(int matrix[][BridgeCount]) // ввод матрицы смежности 
{
    int i, j;
    cout << "Введите количество мостов: ";
    cin >> VertexCount;
    for (i = 0; i < VertexCount; i++) {
        cout << "Введите максимальную грузоподъёмность моста " << i + 1 << ": ";
        cin >> WeightLimit[i];
    }
    for (i = 0; i < VertexCount; i++)
        for (j = 0; j < VertexCount; j++) {
            matrix[i][j] = 0;
            matrix[j][i] = 0;
        }
    do {
        cout << "Введите связи в виде пары вершин (99-конец): ";
        cin >> i;
        if (i != 99) cin >> j;
        if ((i > 0 && i <= VertexCount) && (j > 0 && j <= VertexCount)) {
            matrix[i - 1][j - 1] = 1;
            matrix[j - 1][i - 1] = 1; // матрица смежности симметрична 
        }
        else if (i != 99) cout << "ОШИБКА ввода!" << endl;
    } while (i != 99);
    cout << "Ввод закончен." << endl;
}

void OutputMatrix(int matrix[][BridgeCount])
{
    int j;
    cout << endl << "  ";
    for (int i = 0; i < VertexCount; i++) cout << setw(2) << i + 1; // номера столбцов матрицы      
    cout << endl;
    for (int i = 0; i < VertexCount; i++) {
        cout << setw(2) << i + 1; // номера строк матрицы
        for (j = 0; j < VertexCount; j++) cout << setw(2) << matrix[i][j];
        cout << endl;
    }
}

int isInMap(int Vertex) { // Проверка на нахождение во множестве вершин пути
    for (int i = 0; i < map.mapCount; i++)
        if (map.arr[i] == Vertex) return 1;
    return 0;
}

void FindPath(int Vertex) { // Поиск всех путей в графе
    if (maxWeight > WeightLimit[Vertex]) {
        lastMaxWeight = maxWeight;
        maxWeight = WeightLimit[Vertex];
    }
    CurrentPath[j] = Vertex; // добавление в путь текущей вершины 
    map.arr[map.mapCount++] = Vertex;  // коррекция множества вершин пути 
    j++;
    if (Vertex == pointB - 1) {
        cout << endl << "Найден путь: ";
        for (int i = 0; i < j; i++) // вывод пути           
            cout << CurrentPath[i] + 1 << " ";
        cout << endl << "Его максимальная грузоподъёмность: " << maxWeight << endl;
    }
    else {
        for (int i = 0; i < VertexCount; i++)
            if (!isInMap(i) && matrix[Vertex][i]) // поиск в глубину: выбор продолжения пути без цикла 
                FindPath(i);
    }

    // здесь оказываемся после нахождения очередного пути или в случае попадания в тупик 
    maxWeight = lastMaxWeight;
    map.mapCount--; // исключение из множества вершин пути последней вершины  
    j--;    // возврат в предыдущую вершину 
}

int main() {
    system("chcp 1251");
    char ch;
    InputMatrix(matrix); // ввод матрицы смежности 
    do {
        OutputMatrix(matrix);
        cout << "Введите исходный пункт A: ";
        cin >> pointA;
        cout << "Введите конечный пункт B: ";
        cin >> pointB;
        for (int i = 0; i < BridgeCount; i++)
            map.arr[i] = 0; // инициализация множества вершин пути 
        maxWeight = WeightLimit[pointA - 1];
        lastMaxWeight = maxWeight;
        j = 0;
        FindPath(pointA - 1); // перечисление всех путей        
        cout << "Путей больше нет!" << endl;
        cout << "Повторить поиск? y/n: ";
        cin >> ch;
    } while (ch != 'n');
    return 0;
}

1
  • А я правильно вас понял: ваши "мосты" являются вершинами в вашем графе? То есть физически у вас дороги соединяющие мосты попарно что ли?
    – EzikBro
    15 мая 2021 в 18:18

1 ответ 1

0

Нашёл решение проблемы. Теперь, при достижении конечного пункта, я сравниваю грузоподъёмности мостов, которые находятся на пути. Если встречается мост с меньшей грузоподъёмностью, то меняю значение maxWeight на неё.

Не очень эффективно, но довольно просто (не знаю, почему сразу до этого не додумался)

void FindPath(int Vertex) { // Поиск всех путей в графе
    CurrentPath[j] = Vertex; // добавление в путь текущей вершины 
    map.arr[map.mapCount++] = Vertex;  // коррекция множества вершин пути 
    j++;
    if (Vertex == pointB - 1) {
        cout << endl << "Найден путь: ";
        maxWeight = WeightLimit[CurrentPath[0]];
        for (int i = 0; i < j; i++) { // Вывод пути
            cout << CurrentPath[i] + 1 << " ";
            if (maxWeight > WeightLimit[CurrentPath[i]]) // Расчёт макс. грузоподъёмности
                maxWeight = WeightLimit[CurrentPath[i]];
        }
        cout << endl << "Его максимальная грузоподъёмность: " << maxWeight << endl;
    }
    else {
        for (int i = 0; i < BridgeCount; i++)
            if (!isInMap(i) && matrix[Vertex][i]) // поиск в глубину: выбор продолжения пути без цикла 
                FindPath(i);
    }

    // здесь оказываемся после нахождения очередного пути или в случае попадания в тупик 
    map.mapCount--; // исключение из множества вершин пути последней вершины  
    j--;    // возврат в предыдущую вершину 
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.