Имеется транспортная сеть, включающая мосты. При превышении грузоподъемности некоторого моста он разрушается. Определить максимальный вес груза, который может быть транспортирован из пункта А в пункт В без превышения грузоподъемности находящихся на маршруте движения транспорта мостов.
Я нахожу в графе все пути из А в В и вывожу максимальную грузоподъёмность на данном маршруте. Вот функция для этого:
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;
}