[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

网络流

定义

在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。

继续阅读网络流