Wataru

Зачем в алгоритме сортировки Кана вначале требуется степень или просчёт всех соединений, вроде и без неё всё работает?

Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

Есть ли возможность сортировать не узлы, а рёбра сразу?

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

Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?

Можно. Изолированные узлы - это те в которые ни одно ребро не входит. В алгоритме Кана это те, которые можно вывести до удаления любой вершины.

Раз вам надо обойти врешины в топлолгическом порядке, вам нужна топологическая сортировка. Если у вас только одна корневая вершина, то можно и проще - тут сработает любой обход: в ширину или в глубину из корневой вершины. Если корневых вершин несколько, то надо будет использовать какой-либо алгоритм топологической сортировки. Гуглите его. Есть алгоритм основанный на двух обходах в глубину, или нечто основанное на обходе в ширину.

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

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

Потому что теорема Эйлера. А в процессе шифрования значение для текста вовзводится в степень по модулю n. А для дешифровки возводится в еще одну степень. Поэтому показатель степени ищется по модулю Ф(n).

Проблема в том, что сначала пытаетесь вычислить a^(p-2), а потом взять его по модулю. В задаче числа до 10^9 и если вы попытаетесь вычислить что-то вроде 99999^1000005, то у вас int переменная переполнится, потому что там должны быть миллионы знаков в числе, а в int едва 10 влезает.

Надо брать по модулю при каждом умножении в возведении в степень.

Потому что (a*b)%p = (a%p)*(b%p) % p.

Edit:

Еще две ошибки: считать произведение надо в long long, потму что 10^9*10^9 в int не влезает.
И fast_deg(a, deg/2) надо вызывать только один раз, а то у вас функция работает за O(n) вместо O(log n).

Вы расписали то, что в доказательстве скрывается за "clearly, any 2-factor of G translates into a perfect matching of G' and vice versa". Можно было бы чуть поформальнее, но основная идея правильная. Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

Действительно, полное парсочетание становится циклами. Да, если граф не ориентированный, или содержит "тривальные" циклы (длины 2), то они могут войти в покрытие. Если найдется не полное паросочетание, то в графе будут какие-то непересечающиеся циклы и возможно пути. Он может быть даже не весь покрыт при этом.

Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

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

Функция задана кусочно, да. Но все куски в точках на границах совпадают и разрывов там нет. Функция не гладкая, но все еще непрерывная.

Для целых координат есть glVertex2i.

Еще надо задать в начале преобразование, чтобы координаты соответствовали экрану (один раз):

glutCreateWindow("Game");
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluOrtho2D( 0.0, 600.0, 400.0, 0.0 );

Смотрите внимательно, у вас точка с запятой после цикла. Следующая строка выполняется вне цикла, в котором i и объявлена.

В унимодальной функции разности соседних элементов сначала неотрицательные а потом неположительные. И наоборот, если разности такие, то, очевидно, сначала функция возрастает (возможно, ступенчато) а потом убывает.

Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
2) они все неположительные. Монотонно убывающая функция.
3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.

У вас ошибка в понимании остаточной сети. Раз фиолетовые ребра насыщены, то на самом деле в остаточной сети есть обратные им ребра. И вершина v отлично найдется обходом из s.

Без этих обратных ребер алгоритм поиска потока не работает, ведь у него не будет возможности "отменять" потоки.
Например в графе:

________    
  a-b-c
 /  |   \
s   |     t
\   v   /
  d-e-f

Если сначала найдется поток по пути s-a-b-e-f-t, то дальше единственный способ его дополнить - это взять путь s-d-e-b-c-t, и надо будет "отменить" поток по перекрестному ребру b-e.

Именно max flow, а не mincostmaxflow? Потому что есть очевидное решение с mincostmaxflow.

Граф почти такой же. Раздвоенное ребро. В середину каждого ребра вход из истока пропускной способностью 1 и стоимостью 0. Вдоль ребра в обе стороны такие же ребра - пропускной способности 1 и стоимости 0. Из вершины делаем degree(v) ребер в сток. Каждое пропускной способностью 1 и прогрессивно увеличивающимися стоимостями. Первые ребра стоимостью 1. Вторые - n+1, сделующие (n+1)^2 и т.д.

Стоимость полного потока будет тем меньше, чем меньше максимальная степень, ведь даже одно ребро стоимостью (n+1)^k для вершины степени k+1 хуже чем если бы все вершины имели степень k и ответ был бы n*(n+1)^(k-1).

Если нужен именно просто поток, а не минимальной стоимости, то возможно можно изменить алгоритм потока, чтобы искать его итеративно для всех возможных значений x в вашем графе. Ведь алгоритм итерационно ищет дополняющий путь в остаточной сети. И ответ для x можно использовать в качестве стартового потока для задачи с x+1. Т.е не надо логарифм раз запускать поток для разных графов, а после выполнения увеличить пропускные сопособности нужных ребер на 1 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.

Идея этого усечения в том, что если вы ищите gcd(a, b), то можно также искать gcd(a,a-b). Вот эта замена b' = a-b у вас в коде и происходит.

Вы там поддерживаете инвариант x_i*a+y_i*b = r_i

Сответсвтенно, вам надо пересчитать x_cur и у_cur вместе с изменением r_cur.

У вас есть x_prev*a+y_prev*b = r_prev и x_cur*a+y_cur*b = r_cur. Вам надо составить линейную комбинацию r_prev - r_cur. Ну вычтите одно уравнение из другого и все.

Соответственно вам надо сделать вот это при применении вашего усечения:

x_cur = x_prev - x_cur
y_cur = y_prev - y_cur

Все становится сложно из-за того, что можно второй раз проходить по комнате и при этом не тратить время на гоблина и не получая награды. Мне кажется, можно задачу коммивояжора свести к этой задаче, так что она NP-полная и тут нет быстрого алгоритма. Только перебор или что-то экспоненциальное. Соответственно, оно все работает лишь не небольших гарафах.

Можно применять тот же прием, что и в задаче коммивояжора - расслоите граф на 2^n слоев. Пуст у вас n вершин в изначальном графе. В новом графе каждая вершина соответсвует подмножеству комнат и одной комнате. Фактически, вершина обозначает, какие комнаты вы обошли и где сейчас находитесь.

Ребра есть:
Из вершины ({}, 0) во все вершины ({v},v) ценой goblinTime[v]: это мы можем зайти в лабиринт в любую комнату и должны там гоблина победить.
Из вершины (S, v) в вершину (S,u) ценой path[v,u], если u в S - это мы идем в ранее посещенную комнату.
Из вершины (S, v) в вершину (S+{u},u) ценой path[v,u]+goblitTime[u], если u не в S - это мы идем в ранее не посещенную комнату и бъем там гоблина.

В этом графе на n2^n вершин вам надо найти все кратчайшие пути из начальной ({},0) во все вершины (например, дейкстрой). Потом переберите все вершины в графе (S, v) и, если вершина соответствует комнате с выходом и вы до нее дошли за время не превосходящее время обрушения, то берите сумму количества золота в комнатах в множестве S в качесвте варианта ответа. Из всех них берите максимум.

Вам нужен 2-дольный граф. Левая доля соответствует строкам, правая - столбцам. Из истока ребора в левую долю (ценой ri), из правой доли - в сток (ценой ci). Ребра между долями ценой aij.

Любой разрез тут соответствует покрытию всех вершин. Вы должны разрезать ребро между ij или si или jt что чоответствует покрытию клетки, строки иои столбца.