s****a
发帖数: 143 | 1 The question is to find the balanced spanning tree in O(m*m) , which is the
quesiton in chapeter 13--34 in Ahuja's book: network flow.
Balanced spanning tree is the spanning tree whose difference between the
maximum arc cost and the minimum arc cost is the least one.
Now, I can only find algorithm in O(n*m*m). My method is set every acr as the
samllest one, then cancle the arcs less than it. Then, apply Prim's algorithm.
Finally. choose the samllest one from solutions we will get.
How can I |
|
