Минимальное остовное дерево с использованием алгоритма prim, не знаю, что не так

Question

Прежде всего, я констатирую, что я не прошу ни о каком коде или полных решениях. Опишу проблему:

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

ли эти предположения правильные ?:

1. Здание представляет собой график, комнаты вершины, коридоры ребра, соединяющие их. Следовательно, это неориентированный связный граф.

2. Вы можете решить это, получив вес минимального остовного дерева графика, а затем выполнив полный вес минус вес MST - результат представляет собой сумму весов коридоров, которые можно удалить.

Я реализовал алгоритм Прима для MST и правильный результат для примера случая и для любых других случаев MST, что я нашел в Интернете. Тем не менее, сервер классификации все еще дает мне «неправильный ответ» без какой-либо другой информации. Я не знаю, что случилось. На входе не более 100 вершин и 5000 ребер, поэтому диапазоны не должны быть проблемой. Весы являются целыми числами < = 200. Я использую матрицу смежности для MTS. Пример входных данных:

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

Мои вопросы:

1. Есть ли очевидные ошибки, которые приходят вам на ум? Что следует учитывать, почему это работает для ввода примера и т. Д.
2. Есть ли какие-либо средние размеры тестовых примеров для MST в Интернете, которые я мог бы использовать, чтобы найти проблему?
3. Есть ли другой способ решить эту проблему? Я бы с удовольствием попробовал что-нибудь с сервером сортировки.

Я совершенно не знаком с графиками, поэтому, возможно, что-то не хватает.

Answer 1

1. Здание представляет собой график, комнаты вершины, прихожие ребра, соединяющие их. Следовательно, это неориентированный связный граф.
2. Вы можете решить это, получив вес минимального остовного дерева графика, а затем выполнив полный вес минус вес MST - результатом будет сумма весов коридоров, которые можно удалить.

Да, оба они являются правильными (по модулю придираться, что здание является не граф с номерами в качестве вершин и прихожих как края, но можно рассматривать как таковой). И если вы его рассматриваете таким образом, разница между общим весом исходного графика и общим весом минимального остовного дерева является максимально возможным уменьшением веса, не делая некоторые комнаты недоступными для других (т. Е. Отключая график).

Так я вижу две возможности,

1. У вас есть тонкая ошибка в реализации алгоритма Прима, который срабатывает на TestCase на сервере классификации, но не по testcases вы проверяемых.
2. Сервер классификации имеет неправильный ответ.

Без дополнительной информации, я бы рассмотрел еще 1 вариант.

Есть ли другой способ решить эту проблему? Я бы с удовольствием попробовал что-нибудь с сервером сортировки.

Поскольку вам нужно найти вес MST, я не понимаю, как вы могли это сделать, не найдя MST. Таким образом, другие способы - это разные алгоритмы поиска MST. Kruskal's algorithm Приходит на ум.