let p=a/b,q=(1-c/d)*(1-a/b). The answer of this problem can be showed as:p*q^0+p*q^1+p*q^2+………… That is the sum of a geometric progression which is infinite but 0<q<1.We can get the limit by the formula:p/(1-q)
Obviously, It is about min-cut, which can be solved by max-flow. So, this problem can regarded as the minimum of losing money if we assume SmallR can get all the money and get a total money(sum of wi)at first. Define that, in the min-cut result, the dogs which are connected directly or indirectly to S are 0-gender.otherwise, those to T are 1-gender.We can easily find that the point of a initial-0-gender dog should get a vi weight edge to S.On the other way, initial-1-gender to T. Then, consider the rich men.As to each of rich men, he can appoint only one gender and some dogs.if any one dog he appoint is not the one appointed gender in the result, he can't give SmallR money.How to deal with the rich men in the graph is a difficulty.We can do this, make a new point for a rich man.Then, link the man's point to all points of his dogs by max enough weigh edges(which we can't cut in the min-cut algorithm), and link the man's point to S or T (which depend on that the man's appointed gender is 0 or 1) with a edge of wi weight. lastly run the min-cut(max-flow), we will get the minimum money we will lose. The answer is TotalMoney-LosedMoney. BTW, the issue of g is a piece of cake, we could add it to every special wi but not add it to the total money.
