1 Тема от banin

(1 ответов, оставленных в Offtopic)

Собственно, вопросов появилось несколько - и все они так или иначе связаны с "Алгоритмами:..." Кормена и соавторов:

1.  Есть у кого-нибудь Java CD от них?
Достоверные источники утверждают, что "Алгоритмы..." выходили с реализациями на Java. Возможно, кто-то сможет выложить его?

2. Аналогично, о Tutor Guide.
Есть и еще один дополнительный материал по книге - "Руководство преподавателя". Не совсем понял, что именно нужно сделать, чтоб такую заполучить непосредственно от издателя. Может, есть у кого в электронном виде?

3. Может быть особо сложные/интересные задачи из "Алгоритмов...." могут найти свое место на местном wiki?
Я могу начать, дать, так сказать, "затравку".
А сообществу это интересно? Можно ожидать какого-то содействия?

Пока жду ответа, попробую все-же освоить этот wiki-движок. Может выйдет чего хорошего.

Перейти к разделу: Offtopic

2 Ответ от banin

(2 ответов, оставленных в Problems)

Спасибо. Очень познавательный ответ.

Перейти к разделу: Problems

3 Тема от banin

(2 ответов, оставленных в Problems)

В Southern Subregion 2008 была задача K, которую, в числе прочих, никто во время контеста не решил: http://acm.sgu.ru/problem.php?contest=0&problem=402.

Задача заключается в следующем - найти минимальное по стоимости множество ребер, которые достаточно удалить, чтобы в графе нашлась вершина, после удаления которой граф распадётся на компоненты связности.

Ограничения позволяют провести алгоритм за О(V^4), что вкупе с тем, что задача напоминает задачу о минимальном разрезе, приводит к следующей схеме решения:
Пробуем удалить каждую вершину, некоторым образом преобразовываем граф, и пускаем макспоток за О(V^3).

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

Буду рад любой помощи по этому вопросу.

Перейти к разделу: Problems