題目鏈接

Accumulation Degree

Time Limit:?5000MS	?	Memory Limit:?65536K
Total Submissions:?5388	?	Accepted:?1309

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:

?

Each edge of the tree has an positive capacity.

The nodes with degree of one in the tree are named terminals.

The flow of each edge can't exceed its capacity.

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?x,?y,?z?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

?

給你一棵樹(shù)，每個(gè)節(jié)點(diǎn)作為一個(gè)源頭，只有一條邊的節(jié)點(diǎn)可以視為入海口，每條邊有最大流量，問(wèn)這棵樹(shù)源頭的最大流量。

本題是一個(gè)不定根的樹(shù)，可以用“二次掃描與換根法”。

1、第一次掃描時(shí)，任選一個(gè)點(diǎn)為根，在“有根樹(shù)”上執(zhí)行一次樹(shù)形dp，也就是回溯時(shí)發(fā)生的，自底向上的狀態(tài)轉(zhuǎn)移；

2、第二次掃描時(shí)，從剛才選出的根出發(fā)，對(duì)整棵樹(shù)再進(jìn)行一次dfs，每次遞歸前自頂向下的推導(dǎo)，給出換根后的結(jié)果。就是相當(dāng)于把這條與“父親”相連的邊轉(zhuǎn)換成與兒子相連的邊，進(jìn)行處理。

對(duì)于本題，我們?nèi)芜x一個(gè)點(diǎn)作為根節(jié)點(diǎn)，化成一棵有根樹(shù)。此時(shí)每一個(gè)節(jié)點(diǎn)作為源點(diǎn)的流量是其向下走（子樹(shù)）和向上走（父親）流量之和。求子樹(shù)自然一次dfs，注意u的子節(jié)點(diǎn)v入度為1的時(shí)候，v的子樹(shù)流量為0，u直接加上u，v之間的邊權(quán)即可。

此時(shí)d[x]保存的是以x為根節(jié)點(diǎn)的子樹(shù)的流量和。

對(duì)于我們選定的根節(jié)點(diǎn)root，其向上走的結(jié)果為0，root作為源點(diǎn)最終的結(jié)果已經(jīng)出來(lái)了。

第二次dfs，就是求向上走的流量，此時(shí)父親節(jié)點(diǎn)的最終答案d[u]已經(jīng)算好了，兒子節(jié)點(diǎn)還是以兒子節(jié)點(diǎn)為根的子樹(shù)的流量和d[v]，直接把父親節(jié)點(diǎn)的總流量減去走以這個(gè)兒子為根節(jié)點(diǎn)的子樹(shù)的流量，此時(shí)就是父親節(jié)點(diǎn)走別的路的流量，加到兒子上即可。

注意如果父親節(jié)點(diǎn)的度為1，兒子節(jié)點(diǎn)直接加上c[u,v]（u和v之間邊的邊權(quán)）。

“父親節(jié)點(diǎn)的總流量減去走以這個(gè)兒子為根節(jié)點(diǎn)的子樹(shù)的流量”? ? ? ?d[u]-min(d[x],c[u,v])

“加到兒子上” d[v]+=min(d[u]-min(d[x],c[u,v]),c[u,v])

時(shí)刻注意邊權(quán)與節(jié)點(diǎn)流量的取min。

?

#include <iostream> #include <algorithm> #include <vector> #include <cstring> #define ms(a,b) memset(a,b,sizeof(a)) using namespace std; const int N=2e5+10; struct node {int v,w; // node (): {}node(int v,int w):v(v),w(w){} }; int in[N],d[N]; vector<node>tr[N]; void dfs1(int u,int fa) {for(int i=0;i<tr[u].size();i++){int v=tr[u][i].v;if(v==fa) continue;dfs1(v,u);if(in[v]==1) d[u]+=tr[u][i].w;//當(dāng)兒子度為1的時(shí)候，d[y]=0，不能選d[y] else d[u]+=min(tr[u][i].w,d[v]);} } void dfs2(int u,int fa) {for(int i=0;i<tr[u].size();i++){int v=tr[u][i].v;if(v==fa) continue;if(in[u]==1) d[v]+=tr[u][i].w;else d[v]+=min(d[u]-min(d[v],tr[u][i].w),tr[u][i].w);dfs2(v,u); } } int main() {ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){int n,x,y,z;cin>>n;for(int i=1;i<=n;i++)tr[i].clear();ms(in,0);ms(d,0);for(int i=1;i<n;i++){cin>>x>>y>>z;tr[x].push_back(node(y,z));tr[y].push_back(node(x,z));in[x]++;in[y]++;}dfs1(1,0);dfs2(1,0);int ans=0;for(int i=1;i<=n;i++)ans=max(ans,d[i]);cout<<ans<<endl;}}

?

總結(jié)

以上是生活随笔為你收集整理的POJ 3585 Accumulation Degree 树形dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。