ZOJ Problem Set - 3613
Wormhole is a kind of two-way tunnel between two planets which can make it possible to transport large amounts of resources without time. Of course, building Wormhole has lots of requirements, only some pairs of the planet can build Wormhole and it costs lots of money. Country G is a very big country which has a lot of planets. There are several resource planets in country G. One resource planet can provide for a factory, and a factory need a resource planet to provide resource. Due to various reasons, country G has build some factories in several planets without considering about resource planets. So it depends on Wormhole to transport resource if a factory can't get resource from local. It is your task to make a plan to build Wormholes which can make most factories run and use the least money in this case.
The input consist of multiple cases. For each test case, the first line contains an integer N (0 < N ≤ 200) which indicates the number of planets in country G. Then followed by N lines, each line contains two integers Pi, Si .Pi is the number of factories in planet i, if Si =1, planet i is a resource planet; if Si =0, planet i isn't a resource planet. At most of 4 planets have factories and at most of 4 planets are resource planets. The next line contains an integer M (0 < M ≤ 5000) which indicates the number of pairs of planet which can build Wormhole. Then followed by M lines, each line contains three integers xi, yi, ci, which indicate building Wormhole between planet xi and planet yi costs ci.
The output contains one line per case. It contains the maximum of factories that can get resource and the the minimum of money when the maximum of factories that can get resource.
2 1 0 0 1 1 1 2 3
Author: LU, Yi
Contest: ZOJ Monthly, June 2012