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

kl>Ну так а чем все же не устраивают алгоритмы построения минимального остовного дерева? Есди у тебя задан поток между любыми двумя вершинами, то у тебя действительно полный граф. Только маленькое уточнение — если граф полный, то Прим значительно лучше Краскала, т.к. его сложность — O(n^2), а Краскала — O(mlogn), где m — число ребер. В случае полного графа, нетрудно посчитать, что m = C(n,2) = O(n^2)

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

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

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