Минимальное связующее дерево с использованием алгоритма Прима, не знаю, что не так
Прежде всего, я скажу, что я не прошу какой-либо код или полных решений.
Я опишу проблему:
Вам дается количество комнат в здании и количество прихожих между ними. Каждый коридор соединяет 2 комнаты и имеет вес. Всегда можно попасть в любую комнату. Вы должны уменьшить общий вес всех прихожих, удалив их, распечатав уменьшенный вес.
Верны ли эти предположения ?:
-
Здание представляет собой граф, комнаты — это вершины, коридоры — это ребра, соединяющие их. Поэтому это неориентированный связный граф.
-
Вы можете решить эту проблему, получив вес минимального связующего дерева графа, а затем сделать полный вес минус вес MST — в результате получается сумма весов коридоров, которые можно удалить.
Я реализовал алгоритм Prim для MST, и результат является правильным для примера и любых других случаев MST, которые я нашел в Интернете. Тем не менее, сервер оценок все еще дает мне «неправильный ответ» без какой-либо другой информации. Я не знаю что не так. На входе не более 100 вершин и 5000 ребер, поэтому диапазоны не должны быть проблемой. Веса являются целыми числами <= 200. Я использую матрицу смежности для МТС. Пример ввода:
5 7
1 2 50
2 3 40
3 4 20
4 5 10
1 4 40
3 5 30
В этом случае программа печатает 80. Полный вес 190, минимальный вес 110, поэтому мы можем удалить 190 — 110 = 80
Мои вопросы:
- Есть ли очевидные ошибки, которые приходят на ум? На что нужно обратить внимание, почему это работает для примера ввода и т. Д.
- Есть ли среднего размера тестовые случаи для MST в интернете, который я мог бы использовать, чтобы найти проблему?
- Есть ли другой способ решить эту проблему? Я бы с удовольствием попробовал что-нибудь с сервером оценок.
Я совершенно новичок в графиках, поэтому я могу что-то упустить.
Решение
- Здание представляет собой граф, комнаты — это вершины, коридоры — это ребра, соединяющие их. Поэтому это неориентированный связный граф.
- Вы можете решить эту проблему, получив вес минимального связующего дерева графа, а затем сделать полный вес минус вес MST — в результате получается сумма весов коридоров, которые можно удалить.
Да, оба они верны (по модулю придурка, что здание является не график с комнатами в виде вершин и коридорами в виде ребер, но может рассматриваться как таковой). И если вы посмотрите на это таким образом, разница между общим весом исходного графа и общим весом минимального остовного дерева будет максимально возможным уменьшением веса, не делая некоторые комнаты недоступными для других (т. Е. Отключая график).
Итак, я вижу две возможности,
- У вас есть небольшая ошибка в реализации алгоритма Prim, которая вызывается тестовым набором на сервере классификации, но не тестовыми сценариями, которые вы проверяли.
- Оценочный сервер имеет неправильный ответ.
Без дополнительной информации я бы посчитал 1 более вероятным.
Есть ли другой способ решить эту проблему? Я бы с удовольствием попробовал что-нибудь с сервером оценок.
Поскольку вам нужно найти вес MST, я не понимаю, как вы могли бы сделать это, не найдя MST. Так что другие способы — это разные алгоритмы поиска MST. Алгоритм Крускала приходит на ум.
Другие решения
Других решений пока нет …