Battle for Silver
Piet Hein was a Dutch naval officer during the Eighty Years' War between the United Provinces of The Netherlands and Spain. His most famous victory was the capture of the Zilvervloot (“Silver Fleet”) near Cuba in 1628, where he intercepted a number of Spanish vessels that were carrying silver from the Spanish colonies in the Americas to Spain. Details about this famous naval battle are sketchy, so the description below may contain some historical inaccuracies.
The Silver Fleet consisted of vessels containing silver coins. Piet Hein's basic strategy was simple: tow away a number of vessels from the fleet, in order to capture their contents.
In an attempt to prevent the Dutch from carrying out this plan, the Spanish tied all the ships in their fleet together using huge iron chains. Each vessel in their fleet was fixed to at least one other vessel; any two vessels were connected by at most one chain; and the Spanish made sure that the chains did not cross each other, otherwise they could get tied up into a knot. As an end result, the vessels and the chains connecting them formed a connected, planar graph.
However, the Spanish preventive measures only made their situation worse. As an experienced naval officer, Piet Hein knew that towing away a group of ships was easiest if, for every two ships in the group, the ships were connected by a chain. He called such groups chaingroups.
Piet Hein ordered his men to tow away all the ships in the chaingroup that contained the largest amount of booty, after severing the links with the remaining ships in the Spanish fleet with a few highly accurate canon shots. The total booty in a chaingroup is the total number of silver coins in the vessels that make up the chaingroup.
Given a description of the Silver Fleet, find the value of the chaingroup with the highest amount of booty (i.e., total number of silver coins in the ships that make up the chaingroup).
Each test case is described by the following lines:
Each fleet forms a connected, planar graph.
For each test case, output one line containing a single positive integer: the number of silver coins that is captured by Piet Hein's fleet.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|