Hi all,
I have this task to solve:
Given a weighted directed Graph G(V,E) with weights w(u,v). u, v -
elements of V.
If v(i, j) is element of V then v(j,i) is not.
For each vi Element of V are defined:
Sum of weights of incoming edges: Income(i)
Sum of weights of outgoing edges: Outgo(i)
The balance of the node: Balance(i) = Income(i) - Outgo(i).
An vertice is called positive or negative depending on it's
balance.
I am given set of negative vertices : VBadPayers ( not all negative
vertices)
I will call the set of all positive vertices VTakers.
Imagine edges to be duties. Vertices with negative balances are payers
and edges with positive balances are takers.
Imagine all vertices from V1 to be badpayers.
The task is to reduce balances of all the takers with balances of all
the bad payers. The balances of good payers should stay not changed.
The reducement should be proportional to the sum of weights of all the
paths from a given badpayer to a given taker.
Enjoy:)
Ridvan
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
