首页 > ACM题库 > HDU-杭电 > Hdu 1837 Breweries 待解决 [解题报告] C++
2013
12-23

Hdu 1837 Breweries 待解决 [解题报告] C++

Breweries

问题描述 :

People drink a lot of beer in Romania. For each city i of the N cities of the country (numbered from 1 to N), the amount of beer Bi demanded by its inhabitants is known. In order to satisfy the overall demand, a famous beer company wishes to build K breweries in K distinct cities of Romania. From these breweries, beer will be transported to other cities using the existing road network. Each road connects two distinct cities and has a certain length. Because of the recent floods, the road network of Romania has the shape of a tree: that is, there is exactly one path between any pair of cities. Let’s condier a city i and a brewery located in a city X, which is the closest brewery to i. The cost of transporting beer to the city i is dist(i,X)*Bi, where dist(i,X) is the distance between city i and city X. The beer company wants to choose the locations of the K breweries in such a way that the maximum cost of transporting beer to any city in the country is minimized.

输入:

The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: N (1<=N<=100.000) and K (1<=K<=N). The next N lines contain the beer demands of each city: the ith of these lines contains the value Bi (1<=Bi<=10.000). The next N-1 lines contain 3 integers each: A, B and L (1<=L<=10.000), meaning that there exists a road of length L between city A and city B.

输出:

For each of the T test cases, in the order given in the input, print one line containing the minimum value for the maximum cost of transporting beer, in the case of an optimal placement of the breweries.

样例输入:

1
4 2
3
4
2
7
1 2 10
2 3 21
2 4 57

样例输出:

42
Hint
Explanation for sample input and output: The tree is presented in the figure below. The cities where the breweries were built are colored in yellow (the darker color). The cost of beer transportation equal to 42 is achieved between city 3 and the brewery located in city 2.


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?