Здравствуйте, kl, Вы писали:

Дружище! Мне нравится ход твоих мыслей. Тока я предлагаю по пункту (3) перебирать тупо все вершины. И среди них искать вершину с минимальным p. И ещё ты не правильно указал сложность Дейкстры — ведь мы будем запускть его столько раз, сколько у нас вершин в уже построенной сетке. Но меня всё же берут сомнения что этот алгоритм (жадный вроде, да?) будет получать хоть иногда то, что надо... Ну да ладно, мне в общем-то не так уж нужен точный ответ, хватит и приближённого. Визуализацию, структуры данных и всё, в общем, кроме самого алгоритма написал уже... Через полтора часа надеюсь накидать тупого Кра(у)скала и понтоваться

kl>Аа, я кажись тебя понял. Да, простой Прим нам тут не поможет, т.к. при добавлении новой вершины в дерево (скажем — v), может существовать такая вершина u, что где-то на пути от u к v есть ребро с потоком менее чем p(u,v).
kl>Гхм, ну что тут скажешь... может есть стандартный алгоритм, ктр решает подобное. У меня только мысль пересчитывать пути от v до всех вершин в дереве при добавлении каждой новой вершины. В этом случае мы имеем следующее:
kl>1. Если Дийкстра (O(n^2)) говорит нам, что все пути удовлетворяют условию — min(v1,v2) >= p(u,v), для минимального пути u->v — то мы втупую добавляем v и скачем дальше.
kl>2. Если это не так — то начинается самое интересное. мы запоминаем число p, — сумма всех приращений, которые надо сделать в текущем дереве, чтобы добавить v. v пока не добавляем, а оставляем в очереди. Естественно ребра, которые надо наращивать мы тоже запоминаем.
kl>3. Переходим к следующей вершине после v по степени близости к дереву. Считаем его расстояние до дерева + точно так же суммарное приращение ширин ребер (если необходимо). Если сумма получается меньше, чем у v — добавляем эту вершину, а не v.
kl>4. Вместо пункта 3, можно еще посмотреть а нельзя ли v присоединить не к ближайшей вершине в дереве, а к следующей по удаленности.
kl>Выглядит в общем не очень быстро — грубый анализ дает нам O(сумма степеней вершин * n^2). Что как известно в случае полного графа даст в итоге O(n^3). Но есть пара возможностей для оптимизации. Например если в начале пункта 3, мы понимаем, что разность расстояний до дерева между v и новой вершиной больше суммы приращений, посчитанной на шаге 2 — мы просто добавляем v и продолжаем растить дерево. Плюс, если эта новая вершина собирается приращаться к той же точке в дереве, что и шагом ранее v — ее можно сразу отвергать (ибо минимального суммарного веса уже никак не получится). Т.е. average complexity может будет и не такой плохой.
kl>Ну а если где прогнал — не пинай сильно, это всего лишь мои unstructured thoughts