| Вопрос: Олимпиада х.з. Задача 3 | Добавлено: 29.12.03 06:34 |
Автор вопроса:  Павел | Web-сайт: www.vbnet.ru | ICQ: 326066673 |
|
Задача 3 с какой-то олимпиады. 33 баллов из 200. Имеется N городов (N<=50). Для каждой пары городов (i,j) можно построить дорогу, соединяющую эти города и не заходящую в другие города. Стоимость этой дороги a(i,j) рублей. Написать программу для нахождения самой дешёвой системы дорог, позволяющей попасть из любого города в любой другой. Считается, что вне города дороги не пересекаются. Входные данные: в первой стркое входного файла Input.txt содержится число N. В последующих N строках содержатся по N целых чисел (в i-ой строке - стоимости дорог из i-ого города во все города). (a(i,i)=0). Выходные данные: выходной файл Output.txt должен содержать в первой строке число L - количество дорог, которые требуется построить, в последующих L строках - по паре чисел - номера городов, соединяемых дорогой. Пример Input.txt: 4 0 1 2 2 1 0 2 1 2 2 0 1 2 1 1 0 Пример Output.txt: 3 1 2 2 4 3 4 Вчера вечером немного поразмыслил... Задача простая до ужаса! |
| Ответы | Всего ответов: 7 |
|
Номер ответа: 1 Автор ответа:  Neco ICQ: 247906854 Вопросов: 133 Ответов: 882 |
Web-сайт: Профиль | | #1 | Добавлено: 03.01.04 01:12 |
|
Здесь мне тоже надо "немного поразмыслить". Оффлайн. А вообще здесь наверное, что-то типа нахождение самое короткой непересекающейся ломаной. Считаем за длину стоимость дороги. И ещё вариант: ищем в каждом ряду такой матрице самое маленькое число. Находим одно или несколько и смотря в строку с номером столбца, найденного числа, ищем там ещё одно такое или меньшее число. Если оно там есть повторяем трюк, если нет, то ветвь тупиковая и к этому городу более подходов не искать. Возникает только вопрос: А 100%-но ли это правильное решение? Такие алгоритмы вообще сложно проверять... Ну ничего подумаю ещё и выдам - ответ пока не пиши... |
||
|
Номер ответа: 2 Автор ответа: Павел Администратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #2 | Добавлено: 03.01.04 09:57 |
| Алгоритм такой... Берём любой город, для него находим такой город, дорога до которого стоит меньше всего. Потом берём город, ещё не соединённый дорогой с этими двумя городами, и соединяем его дорогой с тем городом из соединённых дорогой, дорога до которого стоит меньше всего. И дальше в том же духе. | ||
|
Номер ответа: 3 Автор ответа:  SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #3 | Добавлено: 03.01.04 11:08 |
|
Павел! Очевидно, что это неправильное решение! Пример: 1 1 1 1000 1 1 1000 1 1 1 Как будет работать твой алгоритм: возьмем любой город (1). От него наименьшее расстояние (назовем это так), скажем, до 2. Потом возьмем 5-й. (Порядок не имеет значения). Расстояние и до 1-го и до 2-го - 1000! Уже получается больше 1001, хотя правильный ответ - 4! |
||
|
Номер ответа: 4 Автор ответа: ПавелАдминистратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #4 | Добавлено: 03.01.04 13:22 |
|
Ничерта не понимаю... Во-первых, откуда ты взял пятый город? В твоей схеме их 4. Во-вторых, какое ещё расстояние? Расстояния в задаче не фигурируют. |
||
|
Номер ответа: 5 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #5 | Добавлено: 03.01.04 15:33 |
|
Городов 5, я использовал сокращенный вариант матрицы, полный: 0 1 1 1 1000 1 0 1 1 1000 1 1 0 1 1 1 1 1 0 1 1000 1000 1 1 0 "Расстоянием" я назвал цену и даже добавил "От него наименьшее расстояние (назовем это так)" |
||
|
Номер ответа: 6 Автор ответа: ПавелАдминистратор ICQ: 326066673 Вопросов: 368 Ответов: 5968 |
Web-сайт: Профиль | | #6 | Добавлено: 03.01.04 17:56 |
|
Гм.. Действительно, был неправ. А вот если сделать, чтобы порядок всё-таки имел значение? То есть отсортировать массив. |
||
|
Номер ответа: 7 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #7 | Добавлено: 03.01.04 18:23 |
|
Имхо, решение должно быть другим... Только лень думать, каким именно |
||
Страница: 1 |