|Online Judge||Problem Set||Authors||Online Contests||User|
You have been approached by a spy agency to determine the amount of contraband goods that are being traded among several nefarious countries. After being shipped from its country of origin, each container of goods is routed through at least one neutral port. At the port, the container are stored in a warehouse before being sent on their way, so you cannot trace individual containers from their country of origin to their final destination. Satellite cameras can tell you the number of containers travelling in each direction on each leg of the journey. They cannot distinguish individual containers, nor do you have information on the times individual containers have been observed. You know, however, that every container takes the shortest possible route to its destination.
The task is to determine both the maximum and minimum number of containers that could have been travelling from one country to another. The transport network that is observed is an unrooted tree, with countries as leaves and ports as internal nodes. For each edge the number of containers is given in two directions. You know from the description above that no container leaves a port in the direction it came from.
In the figure above we see six countries 1,2,4,5,7,9 and three ports 3,6,8. Although all edges on the route from country 1 to country 4 have a capacity of at least 4, it is not possible to send four container along this route. In that case, in port 6 one of the containers arriving from country 2 would be forced to return, which is forbidden.
This problem was taken from Dennis E. Shasha's monthly column Puzzling Adventures, published in Scientific American, July 2003.
The first line of the input contains a single number: the number of test cases to follow. Each test case describes a single unrooted tree, in the following format:
For every test case in the input, the output should contain a single line with two integers, separated by a single space, the minimum and maximum number of containers transported from fr to to fitting the data given.
1 9 1 6 4 1 2 6 2 1 6 3 4 0 7 3 1 1 9 3 1 1 3 8 6 2 8 4 4 1 8 5 2 1 1 4
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator