By an ingenious combination of warfare and arranged weddings, King Richard IV has gained control
of a few remote areas of south-western Europe. (Actually, he is supposed to have coined the phrase
that ‘marriage is the continuation of war by different means’.) To profit from his new property,
deputies shall be installed at certain roads to collect toll fees from passing travellers.
For each of the new areas, the royal cartographer has provided a simple map with the towns and
major roads: Any two towns are connected by exactly one route (a sequence of roads from one town
to another). To each road, the royal treasurer has assigned a number that indicates the profit he
expects from collecting fees at that road. This number may be negative, which means that the cost
of installing deputies is higher than the income.
Your task is to determine a selection of roads that maximizes the total profit (the sum of the earnings
of all selected roads). It is not required that every town is at the end of a selected road, but the
selection has to be connected: It must be possible to go from any selected road to any other selected
road by using only selected roads (this makes transporting the collected fees safer).
The input consists of a sequence of simple maps. Each map starts with a line containing the number
of roads n, where 1 ≤ n ≤ 100000. Each of the following n lines holds a road description that consists
of three integer numbers a, b and p, where 1 ≤ a, b ≤ 200000 and −1000 ≤ p ≤ 1000. They indicate
the towns a and b at the ends of the road and the profit p of selecting this road. Towns are identified
by unique numbers and roads may be passed in both directions. The sequence of maps is followed
by a line containing a 0.
For each map, output a line containing the maximum profit achievable by choosing a selection of
roads as described above.
4 1 2 -7 3 2 10 2 4 2 5 4 -2 3 1 2 -8 2 3 -8 3 4 -1000 5 14 15 0 15 92 10 92 65 -5 65 35 10 35 89 -30 0
12 0 15
Migrated from old NTUJ.
SWERC 2008
| No. | Testdata Range | Score |
|---|