Posted in: 比赛公告

「FZOI」Round #30 – (ICPC) 公告

经历了漫长的疫情封锁,我们终于会在 5 月份摆脱 COVID-19 的影响回到学校。回到学校前,是否竞赛手感下降、智力下降甚至颜值下降?本次的「FZOI」Round #30 - (ICPC) 就是给各大即将返校的选手准备的训练赛。

本次比赛的题目来自于组题人 @kal0rona 在各大 OJ 上刷到的一些比较适合恢复手感的题目,平均难度在 NOIp 提高组或 Codeforces Div.2 难度之上,但是峰值难度低于 Codeforces Div.2。

本次比赛分成两个 Episode,开始时间分别为 5 月 2 日和 5 月 3 日的下午 14:00 至 17:00。赛后将会提供视频讲解。

为了更好的让选手从这次比赛中得到恢复和训练,本次的比赛允许三人进行组队、并且提前准备模版,但仍然要遵守 ICPC 赛制的纪律。FZOI 成员中被发现任何学术作弊的行为都将会得到严厉的惩罚。

希望这次大家玩得开心。

Posted in: 算法讲稿

上下界网络流 – 学习笔记

标定

考虑每条边的流量范围:$b(u, v) \leq f(u, v) \leq c(u, v)$。

无源汇上下界可行流

首先我们给这条边标入最大限制 $c(u, v) - b(u, v)$,并默认认为该边已经流入了 $b(u, v)$ 的流量,然后我们可以给每个点设置一个 $M_i$ 来进行流量搜集。

如果:

  • $M_i = 0$,那没啥问题。
  • $M_i > 0$,说明下界要求流入的流量更多,所以我们从附加源点 $S$ 连到此点。
  • $M_i < 0$,同理,说明下界要求流出的流量更多,所以我们专门开辟一个通道为此点流出至附加汇点 $T$。

代码: