用C语言实现农场游戏的问题,解法的实现

Problem Description
“Farm Game” is one of the most popular games in online community. In the community each player has a virtual farm. The farmer can decide to plant some kinds of crops like wheat or paddy, and buy the corresponding crop seeds. After they grow up, The farmer can harvest the crops and sell them to gain virtual money. The farmer can plant advanced crops like soybean, watermelon or pumpkin, as well as fruits like lychee or mango.

Feeding animals is also allowed. The farmer can buy chicken, rabbits or cows and feeds them by specific crops or fruits. For example, chicken eat wheat. When the animals grow up, they can also “output” some products. The farmer can collect eggs and milk from hens and cows. They may be sold in a better price than the original crops.

When the farmer gets richer, manufacturing industry can be set up by starting up some machines. For example, Cheese Machine can transfer milk to cheese to get better profits and Textile Machine can spin cony hair to make sweaters. At this time, a production chain appeared in the farm.

Selling the products can get profits. Different products may have different price. After gained some products, the farmer can decide whether to sell them or use them as animal food or machine material to get advanced products with higher price.

Jack is taking part in this online community game and he wants to get as higher profits as possible. His farm has the extremely high level so that he could feed various animals and build several manufacturing lines to convert some products to other products.

In short, some kinds of products can be transformed into other kinds of products. For example, 1 pound of milk can be transformed into 0.5 pound of cheese, and 1 pound of crops can be transformed into 0.1 pound of eggs, etc. Every kind of product has a price. Now Jack tell you the amount of every kind of product he has, and the transform relationship among all kinds of products, please help Jack to figure out how much money he can make at most when he sell out all his products.

Please note that there is a transforming rule: if product A can be transformed into product B directly or indirectly, then product B can never be transformed into product A, no matter directly or indirectly.

Input
The input contains several test cases. The first line of each test case contains an integers N (N<=10000) representing that there are N kinds of products in Jack’s farm. The product categories are numbered for 1 to N. In the following N lines, the ith line contains two real numbers p and w, meaning that the price for the ith kind of product is p per pound and Jack has w pounds of the ith kind of product.

Then there is a line containing an integer M (M<=25000) meaning that the following M lines describes the transform relationship among all kinds of products. Each one of those M lines is in the format below:

K a0, b1, a1, b2, a2, …, bk-1, ak-1

K is an integer, and 2×K-1 numbers follows K. ai is an integer representing product category number. bi is a real number meaning that 1 pound of product ai-1 can be transformed into bi pound of product ai.

The total sum of K in all M lines is less than 50000.

The input file is ended by a single line containing an integer 0.

Output
For each test case, print a line with a real number representing the maximum amount of money that Jack can get. The answer should be rounded to 2 digits after decimal point. We guarantee that the answer is less than 10^10.

Sample Input
2
2.5 10
5 0
1
2 1 0.5 2
2
2.5 10
5 0
1
2 1 0.8 2
0

Sample Output
25.00
40.00

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

4
算法:17,6,25,49,27,65,42,48 按顺序加减得99
2
奇怪的计算器,这个问题具体的解法是什么?
2
素数回文 这个问题的解法是什么
2
求教下,这个问题的C语言的解法是什么呢???
1
求此java基础编程题的解法
1
求此java基础编程题的解法要注释
1
一个子集和算法的问题求解
1
leetcode 965 python3解法求助(self的用法有问题)
0
线性递归序列的问题,递归函数倒推采用C语言的解法
2
求解一个和平方数列求和有关的解法的问题,采用C语言解决这个问题的思路实现怎么做?
1
分别表示该段连续的整数中所有偶数的平方和以及所有奇数的立方和,这个算法问题的C语言的解法,谢谢
1
算法的解法,求方程的根,具体运用的C语言的办法的思路?
0
数据结构综合解决这个棋盘问题的解法,运用C语言编程技术
0
最大子列和问题的算法复杂度分析,不懂是怎么求出来的
3
如何在service层中,进行异步操作?为什么CompletableFuture.runAsync这个方法调用的方法没执行?
0
输出一行中获得礼物的人。如果没有人能得到礼物,输出“no one”,用C语言程序编写的解法
0
平方求和只计算奇数,怎么运用C程序的编写的代码的过程的思路解法去实现的呢?
2
最长递增子序列问题可以在实际的工作中解决什么样的需求?
1
windows10下用命令行启动kafka 报错wmic不是内部或外部命令,环境变量,路径啥的都有,依然报错
2
window.close()方法在chrome浏览器为何有时有效,有时无效?求具体解法