Description: Given to have a tree T, the tree T for each vertex u has a right to w [u], each tree edge [u, v] also has a non-negative edge length d [u, v]. Tree T has to each vertex u can be seen as customers, demand for their services w [u]. Each edge [u, v] of side length d [u, v] can be seen as are transportation costs. If vertex u Department is not set service agencies will be vertex u Services Department needs to have trees along the edge [u, v] transferred to the vertex v Department service agencies, it would take to pay the service fee for the transfer of w [u]* d [u, v]. Shugen Services Department has set up institutions, now in the tree T and a new k Department service agencies, making整棵Transfer Service tree T of minimum cost. The algorithm for a given directed tree T, calculated in the tree T and a new k services agencies transfer the cost of the smallest services.
To Search:
- [transportation] - transportation system，you can seach the
- [kdys] - Express transportation management system
File list (Check if you may need any files):
kmt.cpp
Download