Luogu3128 [USACO15DEC]最大流Max Flow 树上差分

发布于 2017-07-26  2.83k 次阅读


[toggle hide="yes" title="题目" color=""]

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道,隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线,第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力,你需要计算压力最大的隔间的压力是多少。

详见:Luogu3128

[/toggle]

此题不是网络流!

树上差分裸题,将差分思想用在树上。要对整条路径上的点进行操作,可以先考虑对路径的两个端点、LCA以及LCA的父节点进行操作,最后一遍DFS,更新各节点信息。例如在本题中,要将整条路径的点权加1,可以给两个端点分别加1,给LCA减1,再给LCA的父节点减1。完成所有操作后,只需要DFS一遍,处理完当前节点的子节点后,将子节点的权值加在当前节点上,这样即可差分解决问题。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974