🧨 Welcome to my blog!

叫我 Zirnc 或者 ChungZH 都可以~

如无特殊说明,本站内容使用 CC BY-NC-SA 2.5

OI 相关内容同步发表在 我的 HydroOJ Blog我的 Luogu 博客

Latest Articles

View all
· Zirnc

网络流笔记

最大流 概念 容量:$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$。...

Read more
· Zirnc

网络流题集

最大流 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]....

Read more
· Zirnc

CDQ 分治笔记

基本思想 CDQ 分治的基本思想十分简单。如下: 我们要解决一系列问题,这些问题一般包含修改和查询操作,可以把这些问题排成一个序列,用一个区间 $[L,R]$ 表示。 分。递归处理左边区间 $[L,M]$ 和右边区间 $[M+1,R]$ 的问题。 治。合并两个子问题,同时考虑到 $[L,M]$ 内的修改对 $[M+1,R]$ 内的查询产生的影响。即,用左边的子问题帮助解决右边的子问题。 这就是 CDQ 分治的基本思想。和普通分治不同的地方在于,普通分治在合并两个子问题的过程中,$[L,M]$ 内的问题不会对 $[M+1,R]$ 内的问题产生影响。 前置知识:二维偏序 给定 $N$ 个有序对 $(a,b)$,求对于每个 $(a,b)$,满足 $a2<a$ 且 $b2<b$ 的有序对 $(a2,b2)$ 有多少个。 可以将归并排序求逆序对的思路套用过来,这题实际上就是求顺序对。首先根据 $a$ 的大小排序,然后归并排序 $b$,这样就可以忽略 $a$ 元素的影响,因为左边区间的元素的 $a$ 一定小于右边元素的 $a$。归并排序时,每次从右边区间的有序序列取一个元素,然后求左边区间多少个元素比它小即可。 更浅显的解法是,用树状数组代替 CDQ 分治。这里就不赘述。 放个求逆序对的代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void mergesort(int l, int r) { if (l >= r) return ; int mid = (l+r)/2; mergesort(l, mid); mergesort(mid+1, r); int lp = l, rp = mid+1; int i = l; while (lp <= mid && rp <= r) { if (a[lp] > a[rp]) { ans += mid-lp+1; b[i++] = a[rp++]; } else { b[i++] = a[lp++]; } } while (lp <= mid) b[i++] = a[lp++]; while (rp <= r) b[i++] = a[rp++]; for (int i = l; i <= r; i++) a[i] = b[i]; } 例题 一:三维偏序 Luogu-P3810 【模板】三维偏序(陌上花开)...

Read more
· Zirnc

二分图笔记

定义 在图论中,二分图(bipartite graph)是一类特殊的图,又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 $U$ 和 $V$ 的图,使得所有边都是连结一个 $U$ 中的点和一个 $V$ 中的点。 给定一个二分图 $G$,在 $G$ 的一个子图 $M$ 中,$M$ 的边集中的任意两条边都没有共同的端点,则称 $M$ 是一个匹配。 最小点覆盖:选最少的点,满足每条边至少有一个端点被选。 交错路始于非匹配点且由匹配边与非匹配边交错而成。 增广路是始于非匹配点且终于非匹配点的交错路。 特性 二分图中不存在奇环 因为每一条边都是从一个集合走到另一个集合,只有走偶数次才可能回到同一个集合。 König 定理:一个图是二分图当且仅当它的最小顶点覆盖的顶点数等于最大匹配的边数 首先,最小点集覆盖一定 >= 最大匹配,因为假设最大匹配为 $n$,那么我们就得到了 $n$ 条互不相邻的边,光覆盖这些边就要用到 $n$ 个点。现在我们来思考为什么最小点击覆盖一定 <= 最大匹配。任何一种 $n$ 个点的最小点击覆盖,一定可以转化成一个 $n$ 的最大匹配。因为最小点集覆盖中的每个点都能找到至少一条只有一个端点在点集中的边(如果找不到则说明该点所有的边的另外一个端点都被覆盖,所以该点则没必要被覆盖,和它在最小点集覆盖中相矛盾),只要每个端点都选择一个这样的边,就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案。所以最大匹配至少为最小点集覆盖数,即最小点击覆盖一定 <= 最大匹配。综上,二者相等。 二分图判定 染色法:用 $1,2$ 两种颜色标记图中的节点,与一个节点相邻的所有节点的颜色必须和它不同,若标记过程中出现冲突,说明图中存在奇环。使用 DFS 实现。$O(N+M)$。 CF687A NP-Hard Problem 二分图判定裸题。 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 #include <bits/stdc++....

Read more