Let's consider a directed graph with positive edge weights. For every vertex we determine the difference
D = (summary weight of edges directed FROM this vertex)-(summary weight of edges directed INTO this vertex).
We are given the difference D for every vertex. Sum of all the D's is always 0. What is the best algorithm of finding a graph connecting those vertexes, with minimum number of edges.
If this is not clear, there's an example: we have three vertexes and differences for them: D_A = 5, D_B = -20, D_C = 15 (total = 0).
Solution (the best graph connecting those vertexes) would consist of two edges: A--(5)-->B, C--(15)-->B, and it satisfies all the conditions. This example is trivial, but I believe that solution to this problem in general is not simple at all.