floppa322

У вас ошибка в понимании остаточной сети. Раз фиолетовые ребра насыщены, то на самом деле в остаточной сети есть обратные им ребра. И вершина 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 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.

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

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

Если вам можно брать вершины только из одной доли, то это задача set cover (покрытие множества). Каждая вершина в R задает множество в L и вам надо взять минимальное их количество, чтобы все L было покрыто. Это NP-сложная задача и у нее есть только медленные решения, вроде перебора. Еще можно свести ее к задаче целочисленного линейного программирования и решать каким-нибудь солвером.

В сетевом роутинге, в основном, нет* центрального узла с информацией о всей топологии, чтобы искать пути. Так что там вообще не работает Дейкстра, а работают распределенные алгоритмы.

А так, да, на очень специфичных гарфах всеядный алгоритм Дейкстры не самый лучший вариант. И ваш алгоритм тут получается быстрее.

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

DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

Т.е. вроде бы имеет смысл использовать пометки+списки, если у вас заметно больше проверок, чем объединений.

Но на практике там выигрыша нет, ибо редко когда у вас сильно больше проверок. Да и, если у вас много проверок, то оценка O(log*n) - завышена, ведь если вы одну и ту же проверку повторяете, то там пути сжимаются и проверки работают уже за O(1).

Таким образом, DSU от Тарьяна - лучше всех других структур на практике.

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

Теоретически может использоваться любая функция, которая удовлетворяет аксиомам метричности (тождества, положительности, симметричности, треугольника). Которые, в свою очередь, выражают интуитивные представления о понятии "расстояния". Т.е. можно взять любую функцию, проверить, удовлетворяет-ли она указанным аксиомам, и если да - то применять. В данном случае понятия "лучше"-"хуже" нет - этот вопрос выноситься за скобки, и как правило является предметом исследования на этапе предварительного анализа задачи.

Наиболее распространенным меры, применяемые в кластерном, классификационном анализе, в задачах распознавания образов и пр. - уже упомянутая вами эвклидова мера (или метрика L2). Ее модификация - квадрат евклидова расстояния. Манхэттенская мера (или метрика L1), мера Махаланобиса, мера Чебышева, мера Хэмминга, косинусная мера (полезная в многомерном пространстве, но в случае, если много параметров могут иметь нулевые значения), ее модификация - "мягкая" косинусная мера, мера Кульбака — Лейблера (если все значения всех признаков положительны и векторы объектов нормированы на единицу ) и пр.

А бывают еще неметрические меры близости. (т.е. случаи кода используется функция, которая нарушает одну из упомянутых выше аксиом). В общем, не советую задавать вопрос в теоретической плоскости типа "какой мат. аппарат понадобится для решения такой задачи", потому как там, в этом аппарате, можно и закопаться :-). Достаточно ознакомиться с такой вот интересной книгой: Деза Е.И., Деза М.-М. Энциклопедический словарь расстояний. Ну и при большом желании все перечисленные выше метрики, их описание и области применения легко гуглятся.

Что до практического использования этого аппарата - такая функция должна подбираться для каждой прикладной задачи отдельно. Это подтверждается успешным использованием в разных прикладных областях различных специфических мер близости - например, мера Левенштейна и мера Джаро — Винклера (используемые при обработке текстов), мера Хаусдорфа (при работе с подмножествами), мера Вассерштейна (применяется в различного рода транспортных задачах и - неожиданно - в обработке изображений, от распознавания рукописных текстов до диагностики по рентгеновским снимкам), и пр. А иногда выбор и обоснование тех или иных мер в конкретной задаче есть предмет научных статей и даже диссертаций.

В знаменателе — формула полной вероятности. Вот и всё.
p(B) = p(B|A)·p(A) + p(B|¬A)·p(¬A)

Для чего? Да просто p(B) в большинстве случаев хрен поймёшь, и его приходится вычислять непрямо. Например:
A — письмо является спамом
B — в письме есть слово «sex»
Видим в письме слов «sex» — спам ли оно?
Мы можем собрать базу спама со словом «sex», и базу обычной переписки с этим словом, и вычислить p(B|A) и p(B|¬A). А p(A) и p(¬A) вычисляются уже на компе конечного пользователя в зависимости от того, насколько жёстко его спамят.

Пример второй. Каждый тысячный водитель — пьяный. Алкотестер чётко видит алкаша, но останавливает каждого сотого трезвого. Какой процент из приехавших в больницу действительно пьянствуют за рулём?
U — проехавшие через пост водители
A — пьяный
B — алкотестер сработал
Аналогично, p(B) заранее неизвестен, но приходится вычислять по полной вероятности. И вроде бы при таких цифрах один из одиннадцати попавшихся реально пьяный. И это затрудняет антитеррористические меры: если по городу-миллионнику ходит сотня террористов, какая должна быть точность, чтобы не ломать невинные жизни!
UPD: чуть меньше 1/11: p(B|A)=1, p(A)=1/1000, p(B|¬A)=1/100, p(¬A)=999/1000,
итого с сокращением на 1000 будет 1/(1+999/100)=100/1099.

Сила трения. Имеет разрыв в v=0. Ездили когда-нибудь в автобусе или метро каком-нибудь? Пробовали не держаться за поручни? Вот когда оно тормозит, вас вперед тянет некая сила, которая внезапно обрывается, когда транспорт полностью останавливается. Вот это оно фактически. Сила трения действует на транспорт, вам, с вашей точки зрения, кажется, что это вас тянет вперед (хотя это корпус автобуса тянет назад). Но в момент достижения нулевой скорости эта сила трения становится резко равной нулю.

да, первый случай - это декартово произведение. Например, так:
Ω1 = {1, 2, 3, 4}
Ω2 = {0, 4}
Ω3 = Ω1✕Ω2 = {1+0, 2+0, 3+0, 4+0, 1+4, 2+4, 3+4, 4+4}
т.е. суммируем элементы из множества Ω1 с элементами из множества Ω2.

Событие А: из Ω1 выбрали {2, 4}
Событие В: из Ω2 выбрали {4}

теперь прям очевидно независимые.

обычно добавляют, что это же означает, что то, что событие B произошло не даёт никакой информации относительно события A

это не совсем верно. Правильно говорить только о том, что наступление В не влияет на вероятность наступления А.

Ты можешь посмотреть на задачу так: провели ровно 2300 испытаний, какова вероятность, что успех наступил от 600 до 2300 раз.

Так что да, интегральная.

Собственно, ты и сам об этом написал, непонятно тогда в чем загвоздка

В вашем рассуждении ошибка в том, что вы не домножаете условную вероятность 2/6 на вероятность условия. Вы же полную вероятность считатете а P(A) = P(A|B)*P(B)+P(A|!B)*P(!B). У вас P(A|B) = 0, как вы заметили - если они встретились в первом туре, то во втором уже не встретятся. Но все-равно надо 2/6 домножать на P(!B) - вероятность того, что они не встретились в первом туре. А это 1-1/7 = 6/7. В итоге получается все то же 2/6*6/7=2/7.

Но рассуждения автора проще. Можно рассмотреть все независимые элементарные исходы "где в сетке оказался второй игрок". Их 7, они равновероятны по симметрии. Дальше надо домножить на вероятность, что они начиная так встретятся (выиграют свои матчи).

Это не безопасно. Это не UB, но оно не определено стандартом. А значит, компилятор может что-то там соптимизитровать и поломать код.
В документации написано:

Every value of pointer type is one of the following:
* a pointer to an object or function (in which case the pointer is said to point to the object or function), or
* a pointer past the end of an object, or
* the null pointer value for that type, or
* an invalid pointer value.

Т.е. arr у вас, вообще-то, invalid pointer value перед циклом.

Плюс там же написано:

Any other use of an invalid pointer value has implementation-defined behavior.

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

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

Надо смотреть, что там компилятор нагенерировал.

Создайте 2 функции, которые отличаются только вот в этих вот местах.
Вставьте код в https://godbolt.org/

Смотрите ассемблерный код для двух функций.

Может, срабатывает strict aliasing. Видя тип T сомпилятор понимает, что эта переменная не может быть изменена какими-то другими std::byte в соседнем коде и может, например, пропустить загрузку-выгрузку данных в регистр из памяти.

Может вообще что-то другое.

Единственный вариант разобраться - это смотреть на ассемблерный код функций, которые вы и сравниваете. Не каких-то кусков, оттуда надерганных, а функций целиком.