2023-07-29 08:00:00
最大流 Luogu-P1231 教辅的组成 三倍经验： Luogu-P1402 酒店之王 / Luogu-P2891 [USACO07OPEN] Dining G 一眼丁真建图：S->练习册->书->答案->T 然而是错的。很明显，书有可能被多次匹配，与题意不符。 正确的建图：S->练习册->书（拆点）->答案->T 为什么中间层的书要拆点呢？因为一本书不能被重复选用。我们的目的是保证一本书流出的流量只能是 $1$。所以我们把每个代表书的点拆成两个点，左边的点和练习册连边，右边的点和答案连边；左右对应点之间也要连一条容量为 $1$ 的边。 Luogu-P2764 最小路径覆盖问题 定理：最小路径覆盖数=$|G|$-二分图最大匹配数 首先我们假设现在原图内每个点都是一条路径，此时最少路径数为 $n$。 考虑合并路径，当且仅当两条路径首尾相连的时候可以合并。 将点 $x$ 拆成出点 $x$ 和入点 $x+n$，当我们连接 $u, v$ 时，转化为连接 $u, v+n$。将 $S$ 与所有 $u$ 连边，将所有 $u+n$ 与 $T$ 连边。所有边的容量都为 $1$。 在一开始每个点都是一条独立的路径，每次合并将两条路径合并为一条路径，那么最终路径即为点数减去最大匹配数，这样求得的路径覆盖即为最小路径覆盖。 对于输出路径，用 to 记录下一个节点，tag 标记该节点前面是否还有点。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ll dfs(int u, int t, ll flow) { if (u == t) return flow; ll ans = 0; vis[u] = 1; for (int &i = cur[u]; ~i; i = e[i].
2023-07-29 08:00:00
最大流 概念 容量：$capacity(e)$ 表示一条有向边 $e(u, v)$ 的最大允许的流量。 流量：$flow(e)$ 表示一条有向边 $e(u, v)$ 总容量中已被占用的流量。 剩余流量（残量）：$w(e) = c(e)-f(e)$，表示当前时刻某条有向边 $e(u, v)$ 总流量中未被占用的部分。 反向边：原图中每一条有向边在残量网络中都有对应的反向边，反向边的容量为 $0$，容量的变化与原边相反；『反向边』的概念是相对的，即一条边的反向边的反向边是它本身。 残量网络：在原图的基础之上，添加每条边对应的反向边，并储存每条边的当前流量。残量网络会在算法进行的过程中被修改。 增广路（augmenting path）：残量网络中从源点到汇点的一条路径，增广路上所有边中最小的剩余容量为增广流量。 增广（augmenting）：在残量网络中寻找一条增广路，并将增广路上所有边的流量加上增广流量的过程。 层次：$level(u)$ 表示节点 $u$ 在层次图中与源点的距离。 层次图：在原残量网络中按照每个节点的层次来分层，只保留相邻两层的节点的图，满载（即流量等于容量）的边不存在于层次图中。 流的三个重要性质： 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，$f(u,v)\leq c(u,v)$ 斜对称性：每条边的流量与其相反边的流量之和为 0，即 $f(u,v)=-f(v,u)$ 流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V-{s,t},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$ 最大流问题：指定合适的流 $f$，以最大化整个网络的流量（即 $\sum_{(s,v)\in E}f(s,v)$）。 Ford-Fulkerson 增广 增广路指一条从 $s$ 到 $t$ 的路径，路径上每条边残余容量都为正。把残余容量为正（$w(u, v) \gt 0$）的边设为可行边，然后搜索寻找增广路。 找到一条增广路后，这条路能够增广的流值由路径上边的最小残留容量 $w(u, v)$（记为 $flow$）决定。将这条路径上每条边的 $w(u, v)$ 减去 $flow$。最后，路径上每条边的反向边残留容量要加上 $flow$。 为什么增广路径上每条边的反向边的残留容量值要加上 $flow$？因为斜对称性，残量网络=容量网络-流量网络，容量网络不变时，流量网络上的边的流量增加 $flow$，反向边流量减去 $flow$，残量网络就会发生相反的改变。从另一个角度来说，这个操作可以理解为「退流」，给了我们一个反悔的机会，让增广路的顺序不受限制。
2023-05-21 08:00:00
CF-559C Gerald and Giant Chess / AtCoder DP-Y Grid 2 给定一个 $H*W$ 的棋盘，棋盘上只有 $N$ 个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。 $(1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000)$ $O(hw)$ 的暴力 DP 很好想，但是过不了。 假设没有障碍，从 $(1, 1)$ 到 $(i, j)$ 的方案数是 $C_{i+j-2}^{i-1}$（等于 $C_{i+j-2}^{j-1}$）。可以这么理解：可以用 $D, R$ 来表示一条路径，那么从 $(1, 1)$ 到 $(i, j)$ 的路径中有 $i-1$ 个 $D$ 和 $j-1$ 个 $R$。于是问题转化为从 $i+j-2$ 个位置中选 $i-1$ 个放 $D$ 的方案数。 如果有一个障碍，从正面统计方案数很困难，正难则反，考虑将总的方案数减去经过障碍的方案数。假设障碍的位置是 $(x, y)$，终点是 $(h, w)$，经过障碍的方案数就是 $C_{x+y-2}^{x-1} * C_{h-x+w-y}^{h-x}$（乘法原理）。
2023-05-05 08:00:00
我也不知道这是从哪本书上抠来的？ 整除 定义 1：如果 $a$ 和 $b$ 为整数且 $a \ne 0$，我们说 $a$ 整除 $b$ 是指存在整数 $c$ 使得 $b=ac$。如果 $a$ 整除 $b$，我们还称 $a$ 是 $b$ 的一个因子，且称 $b$ 是 $a$ 的倍数。 如果 $a$ 整除 $b$，则将其记为 $a \mid b$，如果 $a$ 不能整除 $b$，则记其为 $a \nmid b$。 定理 1：如果 $a, b$ 和 $c$ 是整数，且 $a \mid b, b \mid c$，则 $a \mid c$。 定理 2：如果 $a, b, m$ 和 $n$ 为整数，且 $c \mid a, c \mid b$，则 $c \mid (ma+nb)$。
2023-04-30 08:00:00
Luogu-P4755 Beautiful Pair 题意 小 D 有个数列 ${a}$，当一个数对 $(i,j)$（$i \le j$）满足 $a_i$ 和 $a_j$ 的积不大于 $a_i, a_{i+1}, \ldots, a_j$ 中的最大值时，小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。 $1\le n\le{10}^5$，$1\le a_i\le{10}^9$。 编程时的问题 对 ST 表不熟悉！ 更 zz 的是，对 lower_bound 和 upper_bound 理解有问题，来复习一下小学知识：lower_bound 是找到“大于等于”的位置，upper_bound 是“大于”。写这道题的时候找小于某数的位置莫名其妙地用了 lower_bound，更没有 -1，完全是随手写的，半天也没察觉到这里有问题。 综上，我是 zz。 思路 考虑分治（据说这是套路），我们找出一个区间 $[l, r]$ 内的最大值位置 $mid$，然后统计所有跨过 $mid$ 的答案，再递归处理 $[l, mid-1], [mid+1, r]$。假设 $mid$ 左边的数是 $a_i$，右边的数是 $a_j$，根据题目得 $a_i * a_j \le a_{mid}$，即 $a_j \le \lfloor\frac{a_{mid}}{a_i}\rfloor$。那么我们枚举 $a_i$，然后用主席树统计右区间内小于 $\lfloor\frac{a_{mid}}{a_i}\rfloor$ 的数的个数。
2023-04-28 08:00:00
消元法及高斯消元法思想 消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。 消元法理论的核心 消元法理论的核心主要如下： 两方程互换，解不变； 一方程乘以非零数 $k$，解不变； 一方程乘以数 $k$ 加上另一方程，解不变。 过程 解方程组： $$ \begin{cases} 2x_1+x_2-x_3=8 \ -3x_1-x_2+2x_3=-11 \ -2x_1+x_2+2x_3=-3 \end{cases} $$ 写成矩阵的形式为： $$ \left[\begin{matrix} 2 & 1 & -1 \ -3 & -1 & 2 \ -2 & 1 & 2 \end{matrix} \middle| \begin{matrix} 8 \ -11 \ -3 \end{matrix} \right] $$ 这种矩阵称为增广矩阵。所谓增广矩阵，即为方程组系数矩阵 $A$ 与常数列 $b$ 的并生成的新矩阵，即 $(A | b)$，增广矩阵行初等变换化为行最简形，即是利用了高斯消元法的思想理念，省略了变量而用变量的系数位置表示变量，增广矩阵中用竖线隔开了系数矩阵和常数列，代表了等于符号。 我们从上到下依次处理每一行，处理完第 $i$ 行后，让 $A_{ii}$ 非 $0$，而 $A_{ji}(j\gt i)$ 均为 $0$。过程如下。
