Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.04.2010, 20:30
Новичок

Отправить личное сообщение для кузен ави Посмотреть профиль Найти все сообщения от кузен ави
 
Регистрация: 20.04.2010
Сообщений: 1

Инкассаторы
Здравствуйте. Нашел очень интерстую задачу на графы. Программированием занимаюсь для себя, на любительском уровне. Может быть у кого-нибудь есть ее решение. Вот само условие:

http://olimpus-belorus.ru/tr03222.htm

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

В стране, где живет Макс, есть N городов. Некоторые из них связанны двусторонними дорогами, которые пересекаются только в городах. Раз в месяц инкассаторы Макса должны доставить деньги в K сберкасс. Все K сберкасс находятся в различных городах. Пока банк Макса небогат и имеет всего одну машину для перевозки денег. Вам необходимо помочь Максу составить маршрут, который, начинается в городе L (в этом городе находится банк Макса), проходит по всем K городам, где находятся нужные сберкассы, и заканчивается также в городе L. Этот маршрут должен иметь минимальную длину (длиной маршрута назовем сумму длин всех дорог, входящих в этот маршрут).

Входные данные: InPut.txt

В первой строке через пробел три числа: N M K, где N - общее количество городов в стране, M - общее количество двусторонних дорог,K - количество сберкасс которые должны посетить инкассаторы(без учета города L).

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

Следующие M строк содержат описание дорог. В каждой строке описывается одна дорога в виде X Y S, где X,Y - номера городов которые связаны дорогой и S - длина этой дороги.

В последней строке дано число L - номер города, где находится банк Макса.

Выходные данные: OutPut.txt

Единственная строка выходного файла должна содержать набор чисел - номеров городов искомого маршрута в порядке обхода. Эти числа должны быть разделены одиночными пробелами. В случае, когда такого маршрута не существует, выходной файл должен содержать одно слово "NO".

Ограничения.

1 < N <= 100
0 < M <= N(N-1)/2
0 < K < 18, K < N
0 < S <= 50000
1 <= L,X,Y <= N
Все входные данные - натуральные числа.
  #2  
Старый 21.04.2010, 02:28
гость

 
Сообщений: n/a

Задача NP-полная, зовётся "traveling salesman".
Речь про "100 городов" в задаче, города-дороги, банки, инкассации - это всё херня для отвода глаз, "вода" как говорят студенты. На самом деле тут в задаче говорят "решите TSP для 18 городов". Все остальное можно (нужно!!!) не читать.

Для n <= 18 решается за O(n^2 2^n) времени динамическим программированием (состояние в динамике - подмножество вершин которые надо посетить и текущая вершин).
  #3  
Старый 21.04.2010, 02:29
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
решите TSP для 18 городов
ни разу не интересная задача
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра