Dinic 算法整理笔记

算法介绍

Dinic 算法是一种用于解决网络流问题的算法,算法复杂度(上界)为 O(n2m)O(n^2m) ,实际要比这个式子好得多(比如用 Dinic 算二分图时的复杂度是 O(mn)O(m\sqrt{n}) )。

Dinic 算法通过对残量网络建立层次图,并在层次图上不断寻找增广路来算出最大流。

残量网络:原图及其反向边构成的图。

反向边:与原边反向的边,原图上的边的反向边的容量为 00 ,每一条边在残量网络上均有其反向边。

层次图:只保留相邻层次之间的边,且不考虑已达到满流的边的图。

层次:可以视作到源点的距离分类。

增广路:残量网络上一条从源点到汇点的边,其所有边中的最小容量为其增广容量。

当前边优化:建立层次图以后,若某个点有一条边已经增广过了,则这条边在当前层次图之后的增广中不会再用到。

阅读全文

[HNOI 2007] 紧急疏散

题目大意

假设每个房间是一个 N×MN \times M 的矩形区域。每个格子如果是 . ,那么表示这是一块空地;如果是 X,那么表示这是一面墙,如果是 D,那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散时,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上可以同时站无数个人。但是,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。

如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

3N, M203 \leqslant N, \ M \leqslant 20

题目链接

【HNOI 2007】紧急疏散 - Luogu 3191

阅读全文

[SDOI 2010] 古代猪文

题目大意

已知远古时期猪文文字总个数为 NN,某一朝代流传的文字是远古时期的 kk 分之一,其中 kkNN 的一个正约数(可以是 11NN),不过具体是哪 kk 分之一,以及 kk 是多少并不知道。考虑到所有可能的 kk,显然当 kk 等于某个定值时,该朝的猪文文字个数为 Nk\frac{N}k。如果所有可能的kk的所有情况数加起来为 PP 的话,那么研究古代文字的代价将会是 GPG^P。 现在他想知道猪王国研究古代文字的代价是多少。答案对 999911659999911659 取模。

输入 NGN、G

N,G1,000,000,000N, G \leqslant 1,000,000,000

题目链接

【SDOI 2010】古代猪文 - Luogu 2480

阅读全文

Markdown学习笔记

基本语法

标题

Markdown支持两种标题的语法,类Setext和类Atx形式。

类Setext采用底线形式,具体地说,是用一行若干个=表示一级标题,若干个-表示次级标题。

1
2
3
4
一级标题
=======
次级标题
-------

类Atx形式是在标题前加入一到六个#表示一到六级标题。这也是本人采用的方法。

1
2
3
4
5
6
# 一级标题
## 二级标题
### 三级标题
#### 四级标题
##### 五级标题
###### 六级标题
阅读全文