算法介绍

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

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

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

反向边：与原边反向的边，原图上的边的反向边的容量为 $0$ ，每一条边在残量网络上均有其反向边。

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

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

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

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

题目大意

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

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

$3 \leqslant N, \ M \leqslant 20$

题目链接

【HNOI 2007】紧急疏散 - Luogu 3191

题目大意

有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n \times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

$2 \leqslant n \leqslant a, b \leqslant 1,000$

题目链接

【HAOI 2007】理想的正方形 - Luogu 2216

题目大意

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

输入 $N、G$。

$N, G \leqslant 1,000,000,000$。

题目链接

【SDOI 2010】古代猪文 - Luogu 2480

基本语法

标题

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

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

1
2
3
4

一级标题
=======
次级标题
-------

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

1
2
3
4
5
6

# 一级标题
## 二级标题
### 三级标题
#### 四级标题
##### 五级标题
###### 六级标题