2023牛客多校训练营2
B . Link with Railway Company
最大权闭合子图问题，树链剖分建图求解
简述最大权闭合子图：现有一有向图，所有点都有一个权值，你需要选择一个子图，使得子图所有点的出边都指向子图内部，问子图最大权
考虑网络流，源点向所有正权点连流量为权值的边，所有负权点向汇点连流量为权值绝对值的边，原图的边流量设为\(inf\)
\[ans = 正权点权值和 - 最大流
\]
本题直接建图会有\(nm\)条边，树链剖分一下建图即可
最大权闭合子图问题，树链剖分建图求解
简述最大权闭合子图：现有一有向图，所有点都有一个权值，你需要选择一个子图，使得子图所有点的出边都指向子图内部，问子图最大权
考虑网络流，源点向所有正权点连流量为权值的边，所有负权点向汇点连流量为权值绝对值的边，原图的边流量设为\(inf\)
本题直接建图会有\(nm\)条边，树链剖分一下建图即可