Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 12.08.2020 20:54:45 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
На основі мови Pascal виникли Object Pascal, Eiffel та Ada.
Події
ПнВтСрЧтПтСбНд
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

Birthday(s):
AVATARLyavan
AVATARmuz
AVATARIgor_1997

Перегляд теми
ACM Контестер | Online Judge System | acm.tju.edu.cn
Автор 3404 - Ant Trip
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 07-12-2009 17:22
http://acm.tju.edu.cn/toj/showp3404.html
Як зробити цю задачу?
Суть для мене понятна - поки можливо шукаєм найбільший шлях який проходить по кожному ребрі один раз (це буде дерево з n-1 ребер і n вершин послідовно з'єднаних). Ребра які ввійшли в цей шлях видаляєм з графа. До результату додаєм 1.
Проблема в тому, як таке реалізувати за 1 сек?
Можливо, є якийсь простіший розв'язок?
Підкажіть, будь ласка, алгоритм або виправте мене якщо я неправий. Спасибі.
Змінив(ла) Witaliy, 07-12-2009 17:29
Надіслати приватне повідомлення
Автор RE: 3404 - Ant Trip
Igor_Lviv NU
Адміністратор

Повідомлень: 14
Звідки: LNU
Зареєстрований: 20.04.07
Опубліковано 08-12-2009 13:23
Підказка: Ейлерові шляхи в графі.
Igor_Y 449531231 IGOR_Lviv NU Надіслати приватне повідомлення
Автор RE: 3404 - Ant Trip
Witaliy
Користувач

Повідомлень: 282
Зареєстрований: 09.02.08
Опубліковано 08-12-2009 17:31
Дякую за підказку, зрозумів.
А тепер більш реалізаційне питання: як зберігати граф (неорієнтований) так, щоб було зручно шукати довільну веришу, яка сполучена з V і видаляти ребро яке їх сполучає? Я спробував відсортований список ребер (M*2 ребер відсортованих по зростанню) - шукати зручно (за О(1)), але видаляти - ні, бо треба шукати два ребра (( A,B ) i ( B,A ). ( A, B ) найдеться за O(1), а з другим більш проблематично).
Як тут бути?

P.S. M<=200000;
Змінив(ла) Witaliy, 09-12-2009 17:30
Надіслати приватне повідомлення
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 1
На сайті немає зареєстрованних користувачів

Користувачів: 4,417
новачок: Elvira
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
22,084,629 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100