标定
考虑每条边的流量范围：\(b(u, v) \leq f(u, v) \leq c(u, v)\)。
Continue reading →
Codeforces 704D:Captain America – 题解
主要思路
一道比较板的上下界网络流。先考虑 \( red > blue \) 的情况，我们把所有点染成红色的然后再做个最大替换即可。我们考虑对每个点、每个横坐标、每个纵坐标做一个点，横坐标和源点、纵坐标和汇点的边需要大概算一下，得出流量范围 \(\frac{cnt_x}{2} \leq flow \leq \frac{d + cnt_x}{2}\)。得出这个范围之后就用板子套一下即可。
「Fortuna OJ」Jul 5th – Group A 解题报告 / 集训队互测 2013
A – 家族
这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。
考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。
网络流
定义
在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。
基本网络流算法
最大流 – Dinic
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。