1798 - Plankton Food

1798. Plankton Food

时间限制 10000 ms 内存限制 128 MB

Only few ZOOs can afford to cultivate all types of plankton food they need to feed to various sea
vertebrates and invertebrates which live in their voluminous aquariums. Some ZOOs might be
from time to time in a short supply of a particular kind of plankton food which is momentarily
difficult to obtain. On the other hand, they also might store some reserves of other plankton
food types which they do not need to spend immediately and those reserves might be huge.
The director is currently in a pressing need for a particular type of plankton food as the construction of a new aquarium with thermal vents is being finished. Fortunately, there are many
colleagues in other ZOOs willing to help. They presented the director with various offers. After
many lengthy calls, the director has built a comprehensive list of all available offers. Now it is
obvious to him that he might need to trade in more steps to obtain the desired food type. In
the first trade step, he would exchange the type A, of which there is plenty in his ZOO, for some
other type B, which in fact he does not need at all but which can be exchanged with another
ZOO for some amount of another type C food, and so on until the final exchange is made which
brings in the appropriate food type.
Looking into the list the director is not sure whether a desired chain of exchanges indeed does
exist. He calls in his economy vice-director and asks for help. The vice-director studies the list
carefully and finally says:
“The amount of food the ZOOs are willing to give in exchange is sometimes bigger and sometimes
smaller than the amount of food they would receive and that depends, of course, on the type of
the food and generosity of a particular ZOO. I cannot say now if the desired chain of exchanges
exists. If it exists, then maybe it would be possible to utilize the offers in such a way that we
receive theoretically an unlimited supply of the desired food for only a small investment of the
food we have. All these possibilities have to be checked.”
You are presented with the list of offers of all other ZOOs. You have to decide if a sequence of
exchanges might be organized in such a way that it brings in a theoretically unlimited supply of
the needed type of the plankton food in exchange for a limited volume of the unnecessary food
(provided that the sources in the other ZOOs are unlimited). We suppose that any exchange
based on a particular trade offer might happen arbitrary number of times.

输入数据

There are more test cases. Each test case starts with a line containing four positive integers T,

F, F_u, F_n. T represents the number of trade offers, F represents the number of types of plankton

food. The types of food are labeled 1, 2, ..., F. F_u is the label of the unnecessary food which the

organizing ZOO is offering, Fn is the label of the necessary food which it wants to obtain by the

trade. Next, there are T lines, each line represents a particular trade offer of a particular ZOO.

The offer is expressed by three values F_r, F_g, U. F_r and F_g are labels of particular food types.

The third number, U, is the natural logarithm (the use of logarithms in the ZOO is very popular

because of the large range of sizes of the animals) of the amount of units of plankton food of
type F_g which the offering ZOO is willing to give in exchange of receiving 1 unit of plankton

food of type F_r. The value of U is a decimal number with at most three digits after the decimal

point and with absolute value less than or equal to 1 000. Note that the identification of the

offering ZOO has been stripped away, as it is not essential for the solution of the problem. The

value of T does not exceed 10 000, the value of F does not exceed 5 000.

The input is terminated by a line with four zeros.

输出数据

For each test case print on a separate line either “TRUE” or “FALSE”. Print “TRUE” if and only

if there is a way to organize the exchanges in such way that an investment of a limited volume

of the unnecessary food type can result in theoretically unlimited supply of the necessary food

type.

样例输入

复制

3 3 1 3
1 2 0.001
2 3 -0.002
3 1 0.001
3 3 1 3
1 2 1.5
2 3 0.5
3 1 -1.999
6 5 1 5
1 2 -0.1
2 3 0.1
3 4 0.1
4 2 0.1
2 5 -0.1
1 5 0
0 0 0 0 · · · \n
 · ·     \n
 · ·      \n
 · ·     \n
 · · · \n
 · ·   \n
 · ·   \n
 · ·      \n
 · · · \n
 · ·    \n
 · ·   \n
 · ·   \n
 · ·   \n
 · ·    \n
 · · \n
 · · · \n

样例输出

复制

FALSE
TRUE
TRUE     \n
    \n
    \n

提交

请先登录

提交