Nearly all of the Kingdom of Byteland is covered by forests and rivers. Small rivers meet to form bigger rivers, which also meet and, in the end, all the rivers flow together into one big river. The big river meets the sea near Bytetown.
There are N lumberjacks' villages in Byteland, each placed near a river. Currently, there is a big sawmill in Bytetown that processes all trees cut in the Kingdom. The trees float from the villages down the rivers to the sawmill in Bytetown.
The king of Byteland decided to build K additional sawmills in villages to reduce the cost of transporting the trees downriver.
After building the sawmills, the trees need not float to Bytetown, but can be processed in the first sawmill they encounter downriver. Obviously, the trees cut near a village with a sawmill need not be transported by river. It should be noted that the rivers in Byteland do not fork. Therefore, for each village, there is a unique way downriver from the village to Bytetown.
The king's accountants calculated how many trees are cut by each village per year. You must decide where to build the sawmills to minimize the total cost of transporting the trees per year. River transportation costs one cent per kilometre, per tree.
Example:
Bytetown 1 1
--- 1 --- 10 --- 5 ---
| 0 |<------| 1 |<-------| 2 |<-------| 3 | 10
--- --- --- <-- ---
|
|3
| ---
----| 4 | 1
---
The nodes {1,2,3,4} are villages and the edges are rivers. The number of trees to be cut is written by the side of each village. The length of each river is written by the edge. 2 sawmills are to be placed.
The solution in this case is to place the mills at villages 2 and 3, which incurs a cost of 4.
Input: The number of villages N (≤ 100), the number of additional sawmills to be built K (≤ 50), the number of trees cut near each village W_i (≤ 10000), and descriptions of the rivers,
Output: The minimal cost of river transportation after building additional sawmills.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky