Ну, пусть f(u) = число путей из вершины u в t. Рекуррентное соотношение: f(u) = сумма f(v), по всем рёбрам (u, v) в графе. Всё будет хорошо, если граф ациклический.
2 2009-10-18 22:03:06
Re: Количество путей в графе (9 ответов, оставленных в Algo)
Если просто сосчитать - то динамическим программированием.
Если же вывести - то перебором. Не забывайте отсекать перебор, как только из текущей вершины нельзя попасть в конечную - тогда сложность перебора будет O(nk), где k = число путей (может быть экспоненциально большим)
3 2009-10-17 17:01:10
Re: Google Code Jam 2009 (12 ответов, оставленных в OlympNews)
manof пишет:
Круто, воще молодцы, от других стран вроде только по одному человеку в финале будет))
Неправда, еще поедет куча китайцев, куда же мы без них то.
А вот - surprise, surprise - в финале будет только один поляк!
4 2009-08-22 02:35:26
Re: Азы С++ (10 ответов, оставленных в Algo)
Или в случае скажем stack<int,vector<int> > d можно обратиться к d[3]?
Нет, нельзя (без низкоуровневых хаков). Этот запрет называется "инкапсуляцией".
2rf пишет:
Ок, что это такое понятно; интересней то, нужно ли это на практике? Ведь по сути мы обрубаем некоторую часть функциональности этого underlying контейнера(не знаю как по русски), почему бы тогда не просто его использовать.
Лично мне не приходилось на разу за всю ACM-ерскую практику указывать нестандартный underlying контейнер в STL'евских классах. А stack<T> я вообще ни разу не использовал. vector<T> это то же самое, но еще и позволяет делать random access.
Но, рискну предложить одно применение - допустим нам надо положить в стек так много элементов, что о?н? ?п?р?о?с?т?о? ?л?о?п?н?е?т они не поместятся в оперативной памяти. Тогда можно было бы написать свой хитрый контейнер, реализующий интерфейс "Back Insertion Sequence", который бы лишние элементы держал не в памяти, а складывал на диск. Ну а так как stack<T> (в отличие от vector<T>) требует доступа лишь к хвосту последовательности, а не к произвольному месту, то это бы, видимо, сильно упростило нам задачу создания такого контейнера.
5 2009-08-19 16:43:34
Re: Азы С++ (10 ответов, оставленных в Algo)
Да и причём здесь "умножение двух длинных чисел"?
Ваш вопрос по азам C++.
6 2009-08-19 16:39:57
Re: Азы С++ (10 ответов, оставленных в Algo)
brainail пишет:
У меня вопрос :
Что значит вот этот типtypedef complex<double> base;то есть он и комплексный и дробный,объясните пожалуйста в чём прелесть типа комплех,и так далее...
Это значит, что он представляет комплексное число x+yi, где i=sqrt(-1) - мнимая единица, а x,y - пара действительных чисел. В complex<double> эти действительные числа представляются типом double. А еще можно быть, например, complex<float> и complex<long double>.
У complex<T> есть два конструктура:
complex(T x, T y) - создаёт число x+yi
complex(T x) - создаёт число x+0i, т.е. чисто действительное число.
Конструкции вида "base w = 1" и "base w(1)" в С++ эквивалентны - они обе означают, что требуется вызвать конструктор класса base, принимающий один аргумент, и причем с типом аргумента, совместимым с тем значением, что ему передают.
7 2009-08-14 13:27:29
Re: Непрерывная задача о рюкзаке (1 ответов, оставленных в Algo)
Дам две подсказки:
1) За линейное время ты можешь найти в массиве медиану (9-я глава в CLRS), а значит и разбить любой массив пополам, так чтобы в одной половинке элементы были меньше чем в другой
2) T(n) = T(n/2) + O(n) имеет решение O(n).
8 2009-08-14 04:38:15
Re: ПО для ACM (10 ответов, оставленных в Offtopic)
* Ubuntu 9.04, со средой GNOME
* gvim, иногда geany. Для java - eclipse. Вместо файлового менеджера - bash.
* gcc 4.3.3, sun-java6-jdk, python 2.6
9 2009-08-14 04:19:38
Re: Petr Mitrichev Contest 3 :: Heavy Disc (2 ответов, оставленных в Problems)
Там решение на основано на теореме из матфизики -
http://en.wikipedia.org/wiki/Harmonic_f … e_property