hdu--6060--RXD and dividing

傷城~ 2022-06-10 01:11 141阅读 0赞

# RXD and dividing #

**Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 1604    Accepted Submission(s): 688**

Problem Description

RXD has a tree   T, with the size of   n. Each edge has a cost.  
Define   f(S) as the the cost of the minimal Steiner Tree of the set   S on tree   T.   
he wants to divide   2,3,4,5,6,…n into   k parts   S1,S2,S3,…Sk,  
where   ⋃Si=\{ 2,3,…,n\} and for all different   i,j , we can conclude that   Si⋂Sj=∅.   
Then he calulates   res=∑ki=1f(\{ 1\}⋃Si).  
He wants to maximize the   res.  
 1≤k≤n≤106  
 the cost of each edge∈\[1,105\]  
 Si might be empty.  
 f(S) means that you need to choose a couple of edges on the tree to make all the points in   S connected, and you need to minimize the sum of the cost of these edges.   f(S) is equal to the minimal cost

Input

There are several test cases, please keep reading until EOF.  
For each test case, the first line consists of 2 integer   n,k, which means the number of the tree nodes , and   k means the number of parts.  
The next   n−1 lines consists of 2 integers,   a,b,c, means a tree edge   (a,b) with cost   c.  
It is guaranteed that the edges would form a tree.  
There are 4 big test cases and 50 small test cases.  
small test case means   n≤100.

Output

For each test case, output an integer, which means the answer.

Sample Input

5 4
    1 2 3
    2 3 4
    2 4 5
    2 5 6

Sample Output

Source

[2017 Multi-University Training Contest - Team 3][]

题意：

给定一棵 n 个节点的树，1 为根。现要将节点 2 ~ n 划分为 k 块，使得每一块与 根节点 形成的最小斯坦纳树的 边权值 总和最大。

解题思路：

这题可以转化为每条边对答案的贡献是多少，每条边尽量被多次用到，则这条边的贡献就越大。那么如何使这条边被尽量多的用到？最多可以被用到多少次？就是下面需要考虑的。拿ab这条边来说，要想多次被用到  取决于b的子树中的节点被分进了多少个点集，分进的点集越多，对答案的贡献越大。b子树中的点最多被分到min(sz(i),k)个点集中，枚举每一条边ai,bi，把他们的贡献累加  就是答案。

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 struct&nbsp;edge 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;v,&nbsp;w;&nbsp; 
 ///子节点，与子节点路径的权重 }; 
 
 edge&nbsp;temp; 
 vector&lt;edge&gt;&nbsp;vec[ 
 1000005]; 
 
 int&nbsp;Size[ 
 1000005]; 
 
 int&nbsp;w1[ 
 1000005]; 
 
 
 void&nbsp;dfs( 
 int&nbsp;u,&nbsp; 
 int&nbsp;pre) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///深搜，求出每个父节点对应子树的大小，以及父节点到各个子节点的路径的权重。 &nbsp;&nbsp;&nbsp;&nbsp;Size[u]&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;l&nbsp;=&nbsp;vec[u].size(); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;l;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;v&nbsp;=&nbsp;vec[u][i].v;&nbsp; 
 ///下一个要遍历的子节点。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(v&nbsp;!=&nbsp;pre) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;w1[v]&nbsp;=&nbsp;vec[u][i].w;&nbsp; 
 ///得出权重 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs(v,&nbsp;u); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Size[u]&nbsp;+=&nbsp;Size[v];&nbsp; 
 ///回溯时，更新子节点我的个数， &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n,&nbsp;k; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(scanf( 
 "%d%d",&nbsp;&amp;n,&nbsp;&amp;k)&nbsp;!=&nbsp;EOF) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(vec,&nbsp; 
 0,&nbsp; 
 sizeof(vec)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(Size,&nbsp; 
 0,&nbsp; 
 sizeof(Size)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(w1,&nbsp; 
 0,&nbsp; 
 sizeof(w1)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n&nbsp;-&nbsp; 
 1;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;u,&nbsp;v,&nbsp;w; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d%d",&nbsp;&amp;u,&nbsp;&amp;v,&nbsp;&amp;w); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp.v&nbsp;=&nbsp;v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp.w&nbsp;=&nbsp;w; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vec[u].push_back(temp); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp.v&nbsp;=&nbsp;u; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vec[v].push_back(temp); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs( 
 1,&nbsp;- 
 1);&nbsp; 
 ///从根节点开始深搜， &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 long&nbsp; 
 long&nbsp;sum&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 2;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///每条路径，被用过的次数最多为min(Size[i],k)，乘上其权重&nbsp;就是他的贡献，然后进行累加。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum&nbsp;+=&nbsp;( 
 long&nbsp; 
 long)w1[i]&nbsp;*&nbsp;min(Size[i],&nbsp;k); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%lld\n",&nbsp;sum); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[2017 Multi-University Training Contest - Team 3]: http://acm.hdu.edu.cn/search.php?field=problem&key=2017+Multi-University+Training+Contest+-+Team+3&source=1&searchmode=source