本文主要是介绍『树形DP·换根法』Accumulation Degree,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
有一个树形的水系,由 N-1 条河道和 N 个交叉点组成。
我们可以把交叉点看作树中的节点,编号为 1~N,河道则看作树中的无向边。
每条河道都有一个容量,连接 x 与 y 的河道的容量记为 c(x,y)。
河道中单位时间流过的水量不能超过河道的容量。
有一个节点是整个水系的发源地,可以源源不断地流出水,我们称之为源点。
除了源点之外,树中所有度数为 1 的节点都是入海口,可以吸收无限多的水,我们称之为汇点。
也就是说,水系中的水从源点出发,沿着每条河道,最终流向各个汇点。
在整个水系稳定时,每条河道中的水都以单位时间固定的水量流向固定的方向。
除源点和汇点之外,其余各点不贮存水,也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
整个水系的流量就定义为源点单位时间发出的水量。
在流量不超过河道容量的前提下,求哪个点作为源点时,整个水系的流量最大,输出这个最大值。
O ( N 2 ) O(N^2) O(N2)解法
加入这是一棵有根树,我们可以直接利用树形DP来进行求解。
设 g [ i ] g[i] g[i]表示以 i i i为根的子树中,以 i i i为源点时的最大流量。
若当前根节点为 r o o t root root,子树的根节点为 s o n son son。
- 当 s i z e ( s o n ) = 1 size(son)=1 size(son)=1时,有且仅有一条河道,可以直接累加权值。
- 当 s i z e ( s o n ) > 1 size(son)>1 size(son)>1时,我们需要将 g [ s o n ] g[son] g[son]和边权 v v v进行比较,显然两者取最小值即可。
状态转移方程就是:
g [ r o o t ] = ∑ s o n ∈ s o n ( r o o t ) { v ( r o o t , s o n ) , s i z e ( s o n ) = 1 m i n ( g [ s o n ] , v ) ,
这篇关于『树形DP·换根法』Accumulation Degree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!