SPOJ: ЗАЯВЛЕНИЕ БАНКРОБА НЕ ЯСНО
Я недавно начал практиковать проблемы теории графов.
Я недавно столкнулся с этой проблемой: BANKROB
Даже после того, как я несколько раз рассмотрел постановку задачи, я не могу понять, как был рассчитан данный результат для примеров.
Я буду признателен вам, если вы можете объяснить примеры тестовых случаев.
Решение
Чтобы понять решения, это помогает визуализировать отображаемые данные. (Конечно, у вас будет компьютерная программа, которая делает это совершенно по-другому.) Исходя из входных данных, дороги в основном выглядят так:
2 - 5 - 7
/ / \ \
1 - 3 - 6 - 8 - 10
\ / \ /
4 9
Чтобы отрезать все пути от 1 до 10, просто удалите точки дросселирования на 5 и 6.
Однако, чтобы отрезать с 5-10 (при условии, что все дороги являются двунаправленными), вы не можете просто удалить 7 и 8 — грабители могут отказаться от 5-3-6-9-10. Таким образом, вы должны отрезать 7, 8 и 9.
Таким образом, в первом примере есть 2 места, которые нужно отрезать, а во втором — 3.
Другие решения
Я объясню один.
Первая строка гласит, что в городе десять перекрестков (узлов) и 14 дорог (краев). Это поможет вам решить проблему, но на самом деле в этом нет необходимости, потому что вы можете узнать это по оставшейся части ввода.
Во второй строке говорится, что цель грабителей — добраться от узла 1 до узла десять. (ваша цель — остановить их).
Каждая строка с третьей по шестнадцатую представляет одну дорогу (ребро). Обратите внимание, что в соответствии с прогнозом, указанным в строке 1, имеется 14 ребер и десять узлов. Эта информация позволяет создавать график.
Чтобы захватить грабителей, вам нужно заблокировать (удалить) как можно меньше узлов, чтобы отделить один узел от десятого. Как выясняется, в этом случае удаление узлов пятого и шестого сделает свое дело, поэтому ответ на вопрос — 2, количество перекрестков, которые нужно удалить.
Теперь, как это вычислить? Ну, это то, что вы изучаете, верно?