I magine that there is max flow like 2, you have source and target connected by two otherwise disjoint paths. But one path is very very long, for exemple 100 edges, and another one is just one edge, then you can push 2 beads in 2 steps, but you must ignore the long path. So the large flow does not help you. Try to imagine that the situation can be made even worse.
How will you route 10 beads? in my graph you need 10 beads. but if you have two paths of the same length you need 5+lengtho of the path-1. So only the size of flow does not metter. 2009/9/30 Prabhu Hari Dhanapal <dragonzsn...@gmail.com> > This is something like a "Flow Network Problem" . > > In the problem , you are just required to push max number of beads to > the receiver - which is the same as Max flow > > The attached file explains some concepts that might help you solve this . > Max flow - min cut theorem , the ford fulkerson algorithm and others > ... > > > > > On Wed, Sep 30, 2009 at 3:46 AM, Miroslav Balaz > <gpsla...@googlemail.com>wrote: > >> So at each step you can move any number of beads form some betwwen some >> pairs (in particular more than one) of adjecent vertices? >> >> It seems to be complicated problem. >> IMHO it is about some routing strategy than graph flow. >> If you do reduction to edge capacit, than the maximum flow and longest >> path on the flow will give you an upperbound (longest path+roof(N/max >> flow)-1) >> >> 2009/9/19 MrM <maleki...@gmail.com> >> >> >>> there is a graph, consisting of N Vertices and some Edges ! >>> each Vertex has a Capacity(for storing Beads), and Capacity of 1st and >>> N-th Vertex is infinite ! >>> there are M Beads in the first Vertex, and we want to move this M >>> Beads to the N-th Vertex with the minimum number of steps ! >>> in each step, we can move some Beads from i-th Vertex to j-th Vertex >>> if and only if there exists an Edge between i-th and j-th Vertex ! >>> the number of Beads at each Vertex cannot exceed its Capacity ! >>> find the minimum number of required steps ! >>> inputs : >>> 1. N 2. adjacency matrix 3. capacity of Vertices [2 ... N-1] >>> 4. M >>> >>> Example : >>> N = 5, >>> adjacency matrix : >>> 0 1 1 0 0 >>> 1 0 0 1 0 >>> 1 0 0 1 0 >>> 0 1 1 0 1 >>> 0 0 0 1 0 >>> capacities : >>> 2-> 2, 3-> 2, 4-> 3 >>> M = 10 >>> Result for example : 6 >>> >>> i will appreciate anyone who write something like Psudo-Code for this >>> problem ! >>> >>> >>> >> >> >> > > > -- > Hari > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
