Bavashi, как раз mn и есть самая точная оценка, ибо m может быть порядка n^2. Т.е. Форд-Беллман будет n^2 на сильно разряженном графе и n^3 на плотном.
Acvik2402, Ваши 2 мапа проверяют, что строку 1 можно преобразовать в строку 2 и обратно. Но есть примеры, когда можно сделать преобразование только в одну сторону. Еще раз: "аб" можно превратить в "аа" ('а'=>'а', б'=>'а'). Обратно - нет, ибо одну 'а' надо оставить, а другую заменить.
Вам надо оставить ваш map1 c его проверками. Но для исключения случая, когда не хватает промежуточных символов для выполнения замен, надо подсчитать количество различных значений в этом мапе (не ключей, а имеено значений из второй строки). Это можно сделать с помощью сета, куда надо сложить вторую строку и проверить его размер.
Acvik2402, Потому что обратный мап не нужен. Вы можете преобразовать "ааб" в "ввв", но не обратно. Вместо обратного мапа заведите сет. Если там 33 элемента, то ответ 0.
Vadim Shorin, Код в вопросе - правильный и выведет с 50 по 5000 элементы.
В вашем рабочем коде какая-то другая ошибка. Может вы где-то память портите, может опечатка банальная. Придется приводить рабочий код. Оставьте только ввод и вывод, можете переименовать переменные, если имена секретные.
Последний комментарий на тему for (i = 0; i < n; ++i) O(n)
Все до этого - это именно последовательные алгоритмы. Там берется количество операций в первом, во втором и складываются.
Drak Lowell, Очень непонятно написано условие. Уточните, пожалуйста.
"путь, который обойдет каждый граф единижны" - У вас что, несколько графов? Вроде как у вас один граф и в нем важные вершины. Вам надо пройтись по всем waypoint вершинам? Конечная точка не важна, но есть ли фиксированная начальная точка?
Waypoint-ы можно обходить в любом порядке? Можно ли заходить в waypoint несколько раз (допустим, кратчайший путь из B в C лежит уже через обойденную A)? Может ли путь заходить в уже обойденные не waypoint-ы (просто вершины графа)? Насколько у вас большой граф, сколько в нем может быть waypoint-ов?
Для начала нужно определиться - окружность должна точно проходить через точки? Или, как на картинке, точки зашумлены?
Во втором случае возникает вопрос, а какая окружность будет для вас наилучшим приближением. Можно вводить разыне метрики ошибки. Например сумма квадратов разностей квадратов расстояний от центра до точек и квадрата радиуса. Или можно минимизировать максимальный такой квадрат разности.
Играясь с метрикой можно получить более простую или сложную задачу, но ответ может быть разным. Особенно в крайних случаях. Например. если почти все точки лежат на очень маленькой окружности, а одна точка где-то далеко-далеко. Одно решение будет взять окружность через все кроме одной далекой точки. Тут сумма квадратов ошибок будет маленькой. Другое решение будет окружностью, проходящей через центр мелкой окружности и дальнюю точку. Тут максимальная ошибка будет меньше.
beduin01, Вот вам надо понять, как эта лента из структуры получается. Потом взять именно этот код и вместо wirte() сделать там read(). Все.
Судя по тому, что у вас в примере "number" идут подряд, то у вас что-то вроде обхода в ширину, но это нелогичный обход для такой древовидной структуры данных. У вас в примере точно нет опечатки? Если там на самом деле в массиве идет "name", "number", "name", "number", то тогда это обход в глубину и все не так сложно.
