【POJ 3585 Accumulation Degree】

题目链接

http://poj.org/problem?id=3585

Description

Trees are an important component of the natural landscape because of their prevention of erosion and the provision of a specific ather-sheltered ecosystem in and under their foliage. Trees have also been found to play an important role in producing oxygen and reducing carbon dioxide in the atmosphere, as well as moderating ground temperatures. They are also significant elements in landscaping and agriculture, both for their aesthetic appeal and their orchard crops (such as apples). Wood from trees is a common building material.

Trees also play an intimate role in many of the world’s mythologies. Many scholars are interested in finding peculiar properties about trees, such as the center of a tree, tree counting, tree coloring. A(x) is one of such properties.

A(x) (accumulation degree of node x) is defined as follows:

  1. Each edge of the tree has an positive capacity.
  2. The nodes with degree of one in the tree are named terminals.
  3. The flow of each edge can’t exceed its capacity.
  4. A(x) is the maximal flow that node x can flow to other terminal nodes.

Since it may be hard to understand the definition, an example is showed below:

A(1)=11+5+8=24
Details:

1->2 11

1->4->3 5
1->4->5 8(since 1->4 has capacity of 13)
A(2)=5+6=11
Details:

2->1->4->3 5
2->1->4->5 6
A(3)=5
Details: 3->4->5 5
A(4)=11+5+10=26
Details:

4->1->2 11
4->3 5
4->5 10
A(5)=10
Details:

5->4->1->2 10
The accumulation degree of a tree is the maximal accumulation degree among its nodes. Here your task is to find the accumulation degree of the given trees.

Input

The first line of the input is an integer T which indicates the number of test cases. The first line of each test case is a positive integer n. Each of the following n – 1 lines contains three integers xyz separated by spaces, representing there is an edge between node x and node y, and the capacity of the edge is z. Nodes are numbered from 1 to n.
All the elements are nonnegative integers no more than 200000. You may assume that the test data are all tree metrics.

Output

For each test case, output the result on a single line.

Sample Input

1
5
1 2 11
1 4 13
3 4 5
4 5 10

Sample Output

26

有点特殊的树形DP题,需要二次DFS+换根法。首先我们可以假定某一点为根(代码中取的是1号节点),设\(D[i]\)表示以\(i\)为根节点的子树,以\(i\)为源点的最大流量,则可以通过\(DFS\)遍历\(i\)的儿子们求得\(D[i]\)。在求\(D[i]\)的时候注意需要考虑\(i\)与其子孙的连边的流量限制,同时,若其子孙为叶子节点,那\(i\)流向它的流量直接就是与其连边的流量。所以可以得出:

\(D[i]=\sum\limits_{j=1}^{sonNum[i]}min(D[j],e[i][j].capacity),j为非叶子节点;e[i][j].capacity,j为叶子节点\)。

那如何得出以某个点为源点和根,整个树(区别\(D\),\(D\)是以它为原点的子树)的最大流量呢?

我们只需要再做一遍DFS就好。设\(F[i]\)表示以\(i\)为源点和根,整个树最大的流量。我们自上而下进行\(DFS\),考虑\(i\)与其儿子\(j\)的关系,对\(j\)来说,一方面它有自己的子树,另一方面它还会有一条边连着原父亲。显然它能流向原子树部分的流量是\(D[j]\),我们需要考虑的是它能流向原父亲的流量值,回顾我们求\(D[i]\)的算法,当它的原父亲现在是个叶子节点,那显然\(F[j]=D[j]+e[i][j].capacity\);当它的原父亲不是叶子节点时,我们能够通过所谓”换根”操作得出流量,同样回顾求\(D[i]\)的算法,当时考虑\(j\)对\(i\)的贡献为\(min(D[j],e[i][j].capacity)\),那么我们只需要从\(F[i]\)中减去这部分就得出了\(i\)能流向非这颗子树的流量了,我们发现这个流量其实就是\(j\)最大能流给\(i\)的流量(如果不考虑\(e[i][j].capacity\)的话)。考虑边流量的限制,此时\(F[j]=D[j]+min(e[i][j].capacity,F[i]-min(D[j],e[i][j].capacity))\)。

综上,从上向下\(DFS\)一遍,最后取所有\(F[i]\)最大值即可。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*