Given a Directed Graph and a ratio R , Where each edge of the graph will contain both Profit and loss value , Is it possible to find such cycles where the ratio of sum of profit and loss will be strictly greater than R

• PREREQUISITE : Bellman-Ford

• EXPLANATION :

Suppose There is a cycle of 'E' edges which follows above condition that means,

where P_i represents Profit of edge and L_i represent loss of each edge.
(P₁ + P₂ +P₃ +... P_E)/(L₁ + L₂ + L₃ +... L_E) > R

=> (P₁ + P₂ + P₃ + ... P_E) > R(L₁ + L₂ + L₃ + ... L_E)

=> P₁ - RL₁ + P₂ - RL₂ + P₃ - RL₃ + ... + P_E - RL_E > 0

=> _{1<= i <= E} ∑ P_i - RL_i > 0

So that it Means, We need to find a positive weighted cycle where each edge of the Cycle will represent P_i - RL_i . It is the exact oppsite of Bellman ford algorithm . That's Why we will take values of P_i as negative value and L_i as positive value . Basically we will mark each edge as
-P_i+RL_i and then Find negative cycle via Bellman ford algoithm .

• RELATED PROBLEM :

Light OJ 1221