「bzoj3681」Arietta「uoj77」A+B Problem

Source

bzoj3681
uoj77

Hint

请先思考后再展开

网络流+数据结构优化建图

Solution

请先思考后再展开

「uoj77」A+B Problem
朴素的最小割建图:每个点向st连b,向ed连w,然后拆一个辅助点,同点间p,符合条件点连辅助点流量INF
然后因为是给前缀中值域区间建边,考虑保留中间状态的权值线段树合并优化网络流建图
「bzoj3681」Arietta
类似,只不过改为树上线段树合并优化二分图匹配

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8d01.html
转载请注明出处,谢谢!