hdu--6060--RXD and dividing

傷城~ 2022-06-10 01:11 255阅读 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

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

Sample Output

  1. 27

Source

2017 Multi-University Training Contest - Team 3

题意:

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

解题思路:

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

代码:

C++ Code











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





#include<bits/stdc++.h>


using 
namespace std;




struct edge

{

    
int v, w; 
///子节点,与子节点路径的权重
};



edge temp;

vector<edge> vec[
1000005];


int Size[
1000005];


int w1[
1000005];




void dfs(
int u, 
int pre)

{

    
///深搜,求出每个父节点对应子树的大小,以及父节点到各个子节点的路径的权重。
    Size[u] = 
1;

    
int l = vec[u].size();

    
for(
int i = 
0; i < l; i++)

    {

        
int v = vec[u][i].v; 
///下一个要遍历的子节点。
        
if(v != pre)

        {

            w1[v] = vec[u][i].w; 
///得出权重
            dfs(v, u);

            Size[u] += Size[v]; 
///回溯时,更新子节点我的个数,
        }

    }

}




int main()

{

    
int n, k;

    
while(scanf(
“%d%d”, &n, &k) != EOF)

    {

        memset(vec, 
0
sizeof(vec));

        memset(Size, 
0
sizeof(Size));

        memset(w1, 
0
sizeof(w1));

        
for(
int i = 
1; i <= n - 
1; i++)

        {

            
int u, v, w;

            scanf(
“%d%d%d”, &u, &v, &w);

            temp.v = v;

            temp.w = w;

            vec[u].push_back(temp);

            temp.v = u;

            vec[v].push_back(temp);

        }

        dfs(
1, -
1); 
///从根节点开始深搜,
        
long 
long sum = 
0;

        
for(
int i = 
2; i <= n; i++)

        {

            
///每条路径,被用过的次数最多为min(Size[i],k),乘上其权重 就是他的贡献,然后进行累加。
            sum += (
long 
long)w1[i] * min(Size[i], k);

        }

        printf(
“%lld\n”, sum);

    }

    
return 
0;

}


发表评论

表情:
评论列表 (有 0 条评论,255人围观)

还没有评论,来说两句吧...

相关阅读

    相关 分治策略Divide and Conquer

    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,通常是递归算法,就是 把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直