HDU 6060 17多校3 RXD and dividing（树+dfs）

Problem Description

RXD has a tree

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

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

启发博客：http://blog.****.net/lz161530245/article/details/76794473

以下题意和题解摘自此博客

题意：给一棵树T，有n个结点。

给一个k，表示有k个集合，我们需要把2,3,4,…n号节点放入集合，要保证k个集合的并集等于{2,3,4,5…n}，并且集合互不相交。(集合可以为空)

然后每次取一个集合Si与{1}求并，得到比如{1,2,3}，那么tempi = f({1,2,3})；f({1}并Si)的意思是把集合内的所有点连接起来的边的权值和。最后把所有权值和相加的到答案。

最后问你能够得到最大的答案。

分析：

我们要想得到最大的答案，那么就要尽可能的去利用这些边，也就是尽可能重复计算这些边。
那么我们想，假设先从叶子节点开始，把这些叶子节点放入一个集合，那么这个集合的temp值就会把所有的边都算一遍。那么下次我们取所有叶子节点的父亲，放入一个集合，那么这个集合的temp值会把除了叶子节点到父亲的那条那边的其他所有边都算一遍。因为集合可以为空，以此类推，我们就可以得到最大的答案。但是如果遇到集合不够的情况，就把剩下的所有点加入最后一个集合。
那么有以上分析，其实就是算每条边会算多少次，比如叶子节点到父亲的那条边会算一次。其实一条边会算多少次跟某个点的所有子孙节点个数有关，就比如样例中，2号点有3个子孙节点，那么2号点连接父节点的那条边会算3+1次。3号点有0个子孙节点，那么3号点连接父节点的那条边会算0+1次。
那么其实问题就是转化为求每个点的子孙节点个数，然后算出每条边要重复计算的次数即可。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<vector>
 4 #include<cmath>
 5 using namespace std;
 6 #define MAXN 1000005
 7 
 8 struct Edge
 9 {
10     int v,w;
11 };//Edge[u]里面存着u连接的v和这条边的权值
12 vector<Edge>vec[MAXN];//容器存每个u对应的v和w
13 int size[MAXN];//每个节点的子节点数
14 int weight[MAXN];//weight[v]记录v点和它父节点的边值
15 
16 
17 void dfs(int u,int pre)//u是当前点,pre是父节点
18 {
19     size[u]=1;//它本身
20     int len=vec[u].size();
21     int vv;//u的子节点
22     for(int i=0;i<len;i++)
23     {
24         vv=vec[u][i].v;
25         weight[vv]=vec[u][i].w;//记录v点和它父节点的边值
26         dfs(vv,u);
27         size[u]+=size[vv];
28     }
29 }
30 
31 int main()
32 {
33     int n,k;
34     while(~scanf("%d%d",&n,&k))
35     {
36         for(int i=1;i<=n;i++)
37         {
38             vec[i].clear();
39             size[i]=0;
40             weight[i]=0;
41         }
42         Edge tmp;
43         for(int i=1;i<=n-1;i++)
44         {
45             int u,v,w;
46             scanf("%d%d%d",&u,&v,&w);
47             tmp.w=w;
48             //tmp.v=u;
49             //vec[v].push_back(tmp);
50             tmp.v=v;
51             vec[u].push_back(tmp);
52         }
53         dfs(1,0);//深搜找出一个子树节点的个数
54         long long sum=0;
55         for(int i=2;i<=n;i++)//只分2-n
56         {
57             sum+=(long long)weight[i]*min(size[i],k);
58         }
59         printf("%lld
",sum);
60     }
61     return 0;
62 }

这种写法比较好理解，但我感觉如果遇到不是按照父子顺序给出的权值的话，这种写法就不太适合，邻接表会好一点

HDU 6060 17多校3 RXD and dividing（树+dfs）

相关推荐