Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Задачка з обласноі олімпіади
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
http://loippo.lviv.ua/fusion/uploads/ol … ements.pdf
Ось посилання на задачу. 2 задача підскажіть як її розв'язати, тому що навіть ідей не маю з чого ж почати.
Офтоп:
Але формулювання задач - ржака 
А по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.
▼Прихований текстА по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.
Аж ніяк. Треба знайти всі цикли (DFS, BFS на вибір), і вибрати мінімальну вершину що входить в якийсь з циклів.
Ну може, я там детально не розбирався, але з тої опери.
Vo_Vik написав:▼Прихований текстА по темі, пошукайте в гуглі задачу комівояжера. Йти на олімпіаду і не знати типових задач.
Аж ніяк. Треба знайти всі цикли (DFS, BFS на вибір), і вибрати мінімальну вершину що входить в якийсь з циклів.
А можна якесь посилання або інформацію на вище названі цикли
Копати теорію графів і глибше. Почавши з вивчення термінів.
DFS (Depth First Search) - пошук у глибину.
BFS (Breadth First Search) - пошук в ширину.
Якщо в двох словах, то в обох алгоритмах ми заводимо список відвіданих вершин. Додаємо туди першу вершину. У BFS при опрацюванні вершини додаємо всі суміжні з нею невідвідані до кінця списку. У DFS - додаємо першу що попалась, і починаємо опрацьовувати її.
Як тільки ми бачимо відвідану вершину що є суміжною з тою що опрацьовується - ми зустріли цикл.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
