На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
"Любые два города могут соединять несколько дорог" Значит ли это, что такой ввод данных возможен:
3 4
1 3 0
1 3 1000
1 2 1
2 3 2 ?
Відредаговано Kostya_135 (2013-01-04 15:07:41)
Поза форумом
Такой вариант возможен
Поза форумом
Прохання уточнити умову задачі відносно обмеження на «небезпеку» дороги:
1) "Пигульська адміністрація президента визначила небезпеку кожної дороги у вигляді числа від 0 (безпечна) до 1000 (дуже небезпечна)."
2) "та С – «небезпеку» дороги (0≤ С ≤ 10000)."
Щиро вдячний за відповідь.
Поза форумом
Опечатка. Исправил. Спасибо.
Поза форумом
"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...." Из первого предложения следует, что если из 1 города можно проехать во второй, то необязательно из второго можно проехать в первый! Во втором предложении утверждается, что из любого города можно проехать в любой! Получаем, что эти два условия противоречат друг другу. И в связи с этим вопрос:"Какое из этих двух утверждений неверно, то есть,если вводится 1 3 10 это значит, что и 3 с 1 соединены ?"
Поза форумом
Kostya_135 написав:
"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...."
Дороги двусторонние! Проехать можно как "туда", так и "обратно".
Поза форумом
Kostya_135 написав:
"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...."
Всегда нужно стараться как можно точнее "перевести" условие задачи на "алгоритмическо-програмистский" язык.
1) "В государстве Пигулии имеется N городов" -> "Есть граф, содержащий N вершин".
Пока про этот граф ничего не знаем.
2) "некоторые из них соединены двухсторонними дорогами" -> "Граф - неориентированный"
Сколько ребер в графе - пока неясно: от нуля, что спорно, до любого числа.
3) "Проехать можно из любого города в любой" -> "Граф содержит одну компоненту связности".
Теперь уже ясно, что ноль рёбер возможно только для графа из 1-ой вершины. Граф может варьироватсья от дерева до полного графа и даже больше().
4) "администрация президента определила опасность каждой дороги в виде числа от 0 (безопасная) до 1000" -> "Граф взвешенный".
5) "Любые два города могут соединять несколько дорог" -> "Возможны кратные рёбра".
Это обсуждалось выше в теме. Алгоритмы для простых графов уже не годятся.
*) и так далее. После перевода становится ясно, что за задача. Неточный "перевод" любой задачи приводит к тому, что участник решает не ту задачу!
Надеюсь, это сообщение подтолкнёт некоторых участников к изучению теории графов, а жюри не усмотрит в нём подсказки.
Поза форумом