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


R>Да, в данной формулировке задача решается именно так, однако, на практике, как я понял вчера формула $$$=k1*length + k2 * width на самом деле неверна. Ведь чем "шире" провод — тем дороже КАЖДЫЙ ЕГО МЕТР, следовательно — $$$=length * width;

R>Здесь необходимо учесть, что width — мы выбираем сами. Может оказаться так, что между (v1,v2) надо выбрать width(v1,v2)>p(v1,v2) чтобы, например, удовлетворить оптимальнее связь между v4,v5 которая проходит по пути v4-v1-v2-v5... Как это обсчитать я не в курсе.

R>К 7ому апреля постараюсь представить что-нить рабочее, если кому интересно

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