У каждого ребра нижнее ограничение пропускной способности 1 (это означает, что поток по этому ребру хотя бы 1, т.е. мы хотя бы раз пройдём по нему), верхнее какое угодно. В графе несколько истоков (понятно каких) + нужно добавить сток (и рёбра в него из всех вершин пропускной способности от 0 до бесконечности). В этом графе нужно найти минимальный поток. Как это делать, описано в статье Макса.
2 2009-10-27 23:31:52
Тема: Дерево отрезков (изменение на отрезке) (5 ответов, оставленных в Feedback)
Мне кажется, что в статье про дерево отрезков, а именно в разделе про изменение на отрезке что-то недосказано.
А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[ i ] новое значение, которое мы хотим записать.
А если не совпали? Видимо, надо посмотреть, стоит ли в данной вершине Val [ i ], и если стоит, то снять и раздать детям (всё-таки, это не так очевидно ;) ).
3 2009-09-13 09:38:35
Re: Задача с 5-ого Открытого Кубка (10 ответов, оставленных в Problems)
Ответ существует для любого n > 4. На разборе рассказывалось решение, в котором несколько раз кидались случайные точки на сферу, а потом делалась проверка. Проверка -- самая сложная часть.
4 2009-09-08 01:30:06
Re: Проблемы с Java на acm.sgu.ru (5 ответов, оставленных в Offtopic)
Могу сказать, что ничего удивительного в том, что получен RE, а не МL, нет: когда программе не хватает памяти, виртуальная машина вылетает с эксепшеном (или еррором), что, видимо, всегда сгушным чекером интерпретируется как RE.
5 2009-09-05 11:37:52
Re: тимус 1087 (3 ответов, оставленных в Problems)
Мне кажется, два цикла следует поменять местами:
двигаемся по dp слева направо счётчиком i :
для каждого m[k] :
...
, потому что в твоём варианте рассматривая кучку i и собираясь выкинуть m[k], ты ещё не можешь быть уверен, что для кучки i у тебя уже посчитан наилучший ответ (поскольку в будущем мы можем обновить ответ для этой кучки, рассматривая другое m[k]), следовательно и переходы из состояния, в котором ответ ещё не посчитан, не имеют смысла
6 2009-08-21 20:15:44
Re: Азы С++ (10 ответов, оставленных в Algo)
Это значит - тип контейнера, который используется стеком для хранения элементов.
7 2009-08-20 19:13:05
Re: Timus 1019 (10 ответов, оставленных в Problems)
Почему бы просто не хранить картинку? Всего 10000 различных координат, поэтому их можно ужать сначала, и потом хранить для каждой точки её цвет.
8 2009-07-25 19:08:18
Re: Сборы в Саратове (18 ответов, оставленных в OlympNews)
А известно ли что-нибудь про базу отдыха? Например, где находится, уютно ли там жить и есть ли интернет (или хотя бы сотовая связь)?
10 2009-07-24 00:05:06
Re: Формат сайта (14 ответов, оставленных в Feedback)
Кстати, было бы здорово (если не сложно/не лень/видна какая-то польза ) когда-нибудь сделать подсветку синтаксиса в коде на страничках алгоритмов (есть много разных, например вот)
11 2009-07-15 20:31:31
Re: Формат сайта (14 ответов, оставленных в Feedback)
Если зайти на форуме в "новые сообщения", то часть страницы будет заполнена вопросиками )
12 2009-07-14 21:42:09
Re: Быстрый поиск среднего элемента. (17 ответов, оставленных в Problems)
В Минске было несколько задач с отбора школьников. Если сейчас ещё идут зеркала, то отсюда и секретность)
13 2009-07-05 16:07:18
Re: Triangles (21 ответов, оставленных в Problems)
O(N^2 * log(N)) ?
Перебираем пару точек, по ней строим два варианта третьей точки, и ищем эти две точки среди всех данных.