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

Во-первых, я заявляю, что не прошу никакого кода или полных решений. Я опишу проблему:

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

Верны ли эти предположения?

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

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

Я применил алгоритм Прима для 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.

Мои вопросы:

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

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


c++ graph weighted
person lcapkovic    schedule 03.03.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

Поскольку вам нужно найти вес MST, я не понимаю, как вы могли бы сделать это, не найдя MST. Таким образом, другие способы — это разные алгоритмы поиска MST. На ум приходит алгоритм Крускала.

person Daniel Fischer    schedule 03.03.2013
comment
Спасибо за ответ. Я решил проблему!! Я нашел похожую проблему в Интернете и заметил, что в их тестовом вводе одно ребро давалось более одного раза с разным весом. Оценщик, вероятно, сделал то же самое, и мой алгоритм не был готов к этому, поэтому я получил неправильный ответ. - person lcapkovic; 04.03.2013
comment
Ах, множественные ребра между одними и теми же двумя вершинами — это, конечно, то, с чем матрица смежности не справляется. - person Daniel Fischer; 04.03.2013