BIT在线求第k大数

在做小学期Day5C题 (在线维护中位数) 时, 由于我没有做过, 也没有想到正解 (对顶堆) , 卡了很久, 最后用一个奇怪的方法做出来了. 发现这个奇怪的做法复杂度稍高, 但是可以扩展. 对顶堆只能维护中位数或固定k的第k大数, 而奇怪做法可以 (伪? ) 在线查找第k大数, k可变, 代价是$O(\log^2 n)$的, $n$为数列长度.

Read More

day6E

题意

正权无向图$G$, 有$n$个点与$m$条边. 你要回答$q$次询问, 每次询问$u,v$两点, 回答对于$u,v$两点, 这张图上有多少条边在它们任意一条最短路上出现.

Read More

__builtin_popcount原理

小学期题用了这个函数, 觉得十分高级, 学习一个.

这个函数用来数二进制数中1的个数. 正常的操作是: 看unsigned int二进制表示下最右端是不是1; 若是1, 则计数器+1, 再右移; 重复32次. 这样的操作需要进行32次int运算, 效率不够高. 这个问题可以二分解决.

Read More

CF630D2F

将每个独立集$V$考虑为原图中被染色的一些顶点, 而在原图中加边后$E'$可以得到一个子图$G'$, 这个子图如果满足一些条件, $V$就是$E'$生成的子图$G'$中的一个独立集. 这些条件为:

  1. 一条边的两端不同时被染色 (或$V$中任意两点间没有边)
  2. 没有孤立顶点被染色 ($V$中的每个点都应当与$E'$中的一条边相连)

Read More

CF620D2E

由于一条路径可以包含一条边多次, 所以如果$a$能经历$k$条边到达$b$, 那就可以经过$k+2n$条边到达$b$, 只需要在路径中随便找一条边不停折返即可. 于是考虑对树黑白染色, (注意结论, 即树是二分图, 从而可以dfs染成黑白两色, 方便考虑) .

Read More

Dinic算法

本文讲解Dinic算法的思路, 算法本身与证明.

关于残余网络增广路等概念的说明, 请看Ford-Fulkerson算法这篇文章. 这里只致力于改进Ford-Fulkerson算法, 得到一个与$F$无关的算法.

问题

$F$较大时, 影响Ford-Folkerson算法效率的主要因素在于: 每次dfs可能可以找到许多条路径, 但是该算法中每次dfs只进行一次增广, 这就导致增广次数与$F$ (可能) 相关. 一种想法是一次dfs多次增广, 但这样做能否成功是取决于dfs顺序的, 于是考虑, dfs顺序如何时, 效率较高呢?

思路

Dinic算法的核心是每次寻找最短的增广路, 并进行增广. 这样做的理由 (既是依据, 也是好处) 是, 每次沿最短增广路增广后, 最短增广路的长度一定不会减少, 稍后会给出证明. 假如有了这一结论, 每次找到最短增广路的长度时, 将该长度的增广路[全部增广], 然后重新寻找最短增广路, 其长度至少增1, 而增广路长度不会超过$|V|$ (因为增广路是简单路径) , 从而增广次数上界$O(|V|)$.

证明

下面证明, 每次沿最短增广路增广后, 最短增广路的长度一定不会减少. 在原图上, 为寻找最短增广路, 从$s$出发bfs, 设第一次到达点$v$的边为$\langle u,v\rangle$, 为点$v$编号$n_v=n_u+1$. 由bfs的特性, 每条边增量 (指该边终点与起点编号差, 可为负值, 后均同) 不超过1. 特别地, $n_s=0,s$为源点. 称这个图为分层图.

此时有结论: 若$n_t$被更新, 那么最短增广路的长度为$n_t$. 为了证明, 可以寻找为$n_t$标号的边的出发点$i$, 再寻找为$i$标号的边的出发点$j$, …, 最终会回到$s$, 并且沿每条边标号增1. 由于每条边增量不超过1, 每条边都增1是从0到$n_t$最快的方法, 从而我们找到了 (一条) 最短增广路$l_{min}$, 并且每个最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$.

下面使用数学归纳法.

(1) 在分层图上沿最短增广路增广1次后, 新图中可能出现一些新的反向边. 若新图中有增广路$l'$, 其中的边的来源有两种可能:

【1边】原分层图中的边 (bfs时经历过的边) $\langle u,v\rangle$, 满足$n_v\leq n_u+1$;

【2边】增广时出现的反向边$\langle v,u\rangle$, 记原边为$\langle u,v\rangle$, 那么由于原边在最短增广路中, 一定满足$n_v=n_u+1$.

那么沿该路径中任何一条边编号增加不超过1, 为了从$0$到达$n_t$仍然至少需要$n_t$条边, 长度没有变短, 所以最短增广路长度没有减少, 并且所有边都仍满足$n_v\leq n_u+1$.

(2) 假设沿最短增广路增广n次后, 最短增广路长度不减少. 当增广$(n+1)$次后, 若图中无增广路, 结论成立. 若图中仍有增广路, 其中的边可能是:

【1边】增广n次后的图中的边$\langle u,v\rangle$, 满足$n_v\leq n_u+1$;

【2边】第$(n+1)$次增广时出现的反向边$\langle v,u\rangle$, 记原边为$\langle u,v\rangle$, 那么由于原边在最短增广路中, 一定满足$n_v=n_u+1$.

类似于上面, 可以证明沿最短增广路增广$(n+1)$次后, 最短增广路长度仍不减少, 并且所有边都仍满足$n_v\leq n_u+1$.

综上, 沿最短增广路增广后, 最短增广路长度不会减少.

优化

首先, 在证明中我们知道: 最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$, 从而我们只考虑递增的边不会出现错误. 实际上, 每次分层完后, 只要找到增广路就可以增广, 不必局限在最短增广路中增广, 这是自缚手脚. 只考虑递增的边的情况下, 情况立刻不同了: 图成为了DAG! 从而, 边$\langle u,v\rangle$能否使用只与$v$可达的点 (记符合条件的点集为$V$, 那么$\forall g \in V$, $n_g>n_v$) 的情况有关, 而与$s$如何到达$u$无关, 从而, 如果某一时刻发现一条边不能使用, 那么在重新bfs (即重新标号) 之前, 无论其他地方如何增广, 其后的边流量只会减少不会增加, 这条边都仍然不能用来增广. 于是可以记录这些边使之只遍历一次, 每次分层至多访问它们$O(|E|)$次.

算法描述

下面的算法只是大致的描述, 没有伪代码那么明确, 重在讲清楚过程, 希望我做到了.

(Dinic算法) 输入: 网络$G(V,E)$ 输出: 最大流$max\_flow$

步骤0. [准备]建立数组$iter[V]$, 定义$max\_flow\gets0$, 用邻接表$G[V]$存储网络;

步骤1. [建立分层图]bfs(s,0), 当bfs(u,n)时, 若$n_u$已定义, 返回; 否则记$n_u=n$, 并对$G[u]$中的所有元素$v$进行bfs(v, n+1). 清零$iter[]$数组.

步骤2. [有增广路吗? ]若$n_t$未定义, 退出算法, 返回$max\_flow$.

步骤3. [寻找增广路]在$G$上DFS, 寻找从$s$$t$的简单路径, 要求该路径上每条边$e\langle u,v\rangle$可用权值$(w_e-f_e)$大于0, 并且$n_v>n_u$. 若找到, 记该路径上的权值最小的边权值为$f$, 否则$f\gets0$. DFS(u)时按顺序遍历$G[u]$, 若$G[u][i]$不可用, $iter[u]\gets iter[u]+1$.

步骤4. [找到了, 更新残余网络]如果$f>0$, 置$max\_flow\gets max\_flow+f$. 对路径上的每条边$e$, 置$f_e\gets f_e+f$. 记其反向边为$e'$, 置$w_{e'}\gets w_{e'}+f$. 返回步骤3.

步骤5. [没有找到]如果$f=0$, 返回步骤1.

复杂度

由于每次dfs都至少使一条边满流 (从而使之无法使用) , dfs次数上界为$O(|E|)$. 在当前弧优化后, 每次dfs经过的边有两种可能性: (1) 是无用边 (2) 在增广路里, 其中 (1) 无用边在一次分层内总共访问$O(|E|)$次, 而 (2) 成功增广的情况中, 增广路长度不超过$|V|$, 每次分层中情况 (2) 的总复杂度上界为$O(|E||V|)$, 从而每次分层的复杂度上界为$O(|E||V|+|E|)=O(|E||V|)$, 从而Dinic算法总的时间复杂度为$O(|E||V|^2)$.

模板

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
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数, 视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge{
ll to, w, rev;
};
vector<edge> G[V];
int num[V], iter[V];
int s, t;//源点和汇点, 是全局变量

ll max_flow();
ll dfs(ll u, ll f);
void bfs();
void add_edge(ll from, ll to, ll w);

ll max_flow() {
ll f = 0, flow = 0;
while(true) {
memset(iter, 0, sizeof(iter));
bfs();
if(num[t] == -1) return flow;
while(f = dfs(s, INF)) {
flow += f;
}
}
}
ll dfs(ll u, ll f) {
if(u == t) return f;
ll flow;
for(int &i = iter[u]; i < G[u].size(); i++) {
edge &e = G[u][i];//注意是引用, 需要直接修改原图
if(e.w > 0 && num[u] < num[e.to]) {
if(flow = dfs(e.to, (f > e.w ? e.w : f))) {
//min函数有些编译器不给过, 所以用三目
e.w -= flow;
//直接修改容量而非同时记录f和w, 只是为了方便
G[e.to][e.rev].w += flow;
return flow;
}
}
}
return 0;
}
void bfs() {
memset(num, -1, sizeof(num));
queue<int> que;
que.push(s);
num[s] = 0;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = 0; i < G[u].size(); i++){
edge &e = G[u][i];
if(e.w > 0 && num[e.to] < 0) {
num[e.to] = num[u] + 1;
que.push(e.to);
}
}
}
}
void add_edge(ll from, ll to, ll w) {
G[from].push_back(edge{to, w, G[to].size()});
G[to].push_back(edge{from, 0, G[from].size() - 1});
}

如有发现模板的错误请联系我指正, 我将不胜感激.

网络流

最大流问题

举个例子, 互联网上有几台计算机, 某些计算机之间建立了一定带宽的有向连接. 目标是将数据从某台指定的计算机$s$ (称为源点) 传输到$t$ (称为汇点) , 求单位时间内最多能传输多少数据.

有许多类似的问题, 都可以抽象成类似的网络流问题, 上面的问题是一个 (单源单汇) 最大流问题. 形式化地描述, 即为:

对无重边与自环的有向图$G(V,E)$, 若每条边$e\in E$有一个权值$w_e$ (称作该边的容量) , 且$s\in V,t\in V$, 称该图为一个网络. 若一个有向图$G'(V,E)$满足: $G'$$G$完全相同, 除去每条边$e\in E$有另一个权值$f_e$ (称作该边的流量) 以外; 并且对$\forall u\in V,u\ne s,u\ne t$满足$\sum\limits_{e=\langle u,v\rangle}{f_e}=\sum\limits_{e=\langle v,u\rangle}{f_e}$ (即流入每个顶点的流量等于流出的流量) , 那么称该有向图$G'$为网络$G$上的一个流, 该流的流量$f$定义为$\sum\limits_{e=\langle s,u\rangle}{f_e}$. 一个网络的最大流是指该网络的所有流中流量最大的那个.

通常在不引起歧义的情况下, 并不区分最大流最大流的流量.

对上面的抽象模型, 解决最大流问题的算法有两类: 增广路算法和预流推进算法. 最常用的是增广路算法中的 Ford-Fulkerson 算法和​ Dinic​ 算法. 这里将常见的算法罗列如下:

算法名 算法分类 复杂度
Ford-Fulkerson算法 增广路 $O(FE)$
Dinic算法 增广路 $O(n^2m)$
HLPP (我也不会) 预流推进 $O(n^2\sqrt{m})$

Ford-Fulkerson算法

本文讲解Ford-Fulkerson算法的思路, 算法本身与证明, 最后会给出模板. Ford-Fulkerson算法是增广路算法的一种, 用于求解最大流问题, 不明背景请看网络流这篇文章.

分析

朴素算法

朴素的想法 (的一种) 是这样的: 在图中DFS, 一旦找到一条从s指向t并且可以在这条路径上添加流量 (即: 每条边$e$都满足$f_e<w_e$) , 那么就在这条路径的所有边上同时不断添加流量, 直到无法再添加 (即: 某条边$e$$f_e=w_e$) . 直到无法再找到任何这样的路径, 即得到最大流. 如下图.

朴素想法求最大流

上面的图中, 黑色为边的容量, 红色为边的容量. 图1为原来的网络, 其中1为源点, 6为汇点. 图二为DFS时可能得到的一个图, 可以看到上面的算法在这里就会停止. 而图三是该网络的最大流. 可以轻松地验证这一点, 因为从1出发的边都已经满流了, 无法再增加新的流量. 注意, DFS可能得到最优解, 但不是一定得到最优解.

所以上述的算法是错误的. 但是它错在哪里呢?

改进

观察图3, 这个流比图2多的流如图4:

朴素想法与最大流之差

从图4看, 它是把图2中$2\rightarrow4$已有的流量1 “推了回去” 而产生的. 这也正是增广路算法的核心所在. 但是, 这看起来不可理喻: 原图中没有的边, 为什么凭空造出来一条就正确呢?

解释

仔细观察图2和图3, 就会发现, $4\rightarrow6$的边流量没变, 仍然是1. 但是, $2\rightarrow4$的流量没有了, 那最大流中谁为4提供那一个流量呢? 显然是$1\rightarrow3\rightarrow4$的路径. 同理, $1\rightarrow2$的流量也没有变, 它从$2\rightarrow5\rightarrow6$的路径流出去了. 这就可以想象成, 节点4不知道是谁给他的流量, 也就是在这个过程中4的上游的信息被屏蔽了, 同时2的下游的信息也被屏蔽了. 只要有人能为4提供流量, 他就什么都不知道. 同样的, 只要有人能从2运走流量, 他也什么都不知道. 这样, 在新的流中, 原本只有一份的流量, $1\rightarrow3\rightarrow 4$流走了一份, $1\rightarrow2\rightarrow5$又流走了一份, 所以流量+1.

所以, $\langle u,v\rangle$的反向边$\langle v,u\rangle$的意义就是: 在$\langle u,v\rangle$有流$f$的时候, 如果有一个路径可以从$v$流入 (称其前面的那段路经为上游) 再从$u$流出 (称其后的那段路径为下游) 且流为$f_0\le f$, 那么就可以认为上游为$v$提供原来的一部分流$f_0$, 而从$u$流入的那些$f_0$ “改道” 从下游流出了.

上面的做法, 可以算作对朴素DFS做法的一个修正, 大概可以理解为: 避免了因DFS顺序不确定而导致的错误.

于是对一个流, 可以对图上所有有流$f$的边$\langle u,v\rangle$建立反向边$\langle v,u\rangle$, 其容量为$f$. 这样得到的新的图称为残余网络, 残余网络上从$s$$t$的路径叫做增广路. 在残余网络上进行dfs沿着增广路来添加流, 这就是Ford-Fulkerson算法.

算法描述

对网络上的每个流$G(V,E)$, 定义与之对应的残余网络$G'(V,E')$: 若$f_e>0(e=\langle u,v\rangle\in E)$, 那么$e\in E'$$rev(e)=\langle v,u\rangle\in E'$, 并且$w_{rev(e)}=f_e,f_{rev(e)}=0$. $E'$中的元素只有刚才描述的那些. 那么算法可以描述为:

Ford-Fulkerson算法

输入: 网络$G$ (一个图$G(V,E)$, $E$中的边$e$有权重$w_e\in\mathbb{N_+}$) , $max\_flow=0$

输出: 该网络上的最大流的流量$f$

步骤0. [建立反向边]定义$max\_flow\gets0$, 用邻接表G[V]存储网络; 对$E$中的每条边$e=\langle u,v\rangle$, 作其反向边$e'=\langle v,u\rangle$, 并置$w_{e'}\gets0$.

步骤1. [寻找增广路]在$G$上DFS, 寻找从$s$$t$的简单路径, 要求该路径上每条边可用权值$(w_e-f_e)$大于0. 若找到, 记该路径上的权值最小的边权值为$f$, 否则$f\gets0$.

步骤2. [找到了, 更新残余网络]如果$f>0$, 置$max\_flow\gets max\_flow+f$. 对路径上的每条边$e$, 置$f_e\gets f_e+f$. 记其反向边为$e'$, 置$w_{e'}\gets w_{e'}+f$. 返回1.

步骤3. [没有找到]如果$f=0$, 输出$max\_flow$, 算法结束.

最大流不会超过从$s$出发的所有边的边权和. 而该算法中每次进入步骤1后, $f$总是正整数 (也有$f=0$的情况, 此时算法结束) , 所以该算法对整数总是有限的. 若记最大流流量上界为$F$, 则该算法最多进入步骤1$(F+1)$次, 而每次进入步骤1需要$O(|E|)$的复杂度进行搜索. 所以总的时间复杂度是$O(F|E|)$. 但这个复杂度上界是很松的, 实际用起来效率比较高, 所以有时即使估计复杂度偏高也可以使用. 对$F$较小的情况则可以轻松应对.

证明

在Ford-Fulkerson算法结束后的残余网络上没有$s\rightarrow t$路径, 所以 (残余网络上) 从$s$可达的所有点构成的集合$S$不包含$t$. 记$T=V-S$, 那么$T$不空, 并且$T\cap S=\varnothing$.

结论1: 从$S$指向$T$ (满足$u\in S,v\in T$) 的边$e=\langle u, v\rangle$都应当满流, 即$w_e=f_e$. 否则, 由于从$s$可达$u$, $s$也可以从$s\rightarrow u\rightarrow v$到达$v$, 那么$v\in S$, 矛盾.

结论2: 从$T$指向$S$ (满足$u\in T,v\in S$) 的边$e=\langle u,v\rangle$流量必为0. 否则, $s$可由其反向边到达$u$; 即: 流入$S$的流量为0. (反向边就是在这里用到的)

对于任意一个流, $S-\{s\}$中的点流入的流量都等于流出的流量, 那么流入$S-\{s\}$的流量$f_{in}$等于从$S$流向$T$的所有边的流量和$S_f$, 这个和不超过从$S$流向$T$的所有边的容量和$S_w$, 写在一起就是$f_{in}=S_f\le S_w$. 从而从$s$流出的流量$f_s$一定不超过$S_w$, 因为$f_s$应当是$f_{in}$的一部分. 即$f_{s}\le S_w$, 这是对任意流的结论.

而对于残余网络 (注意残余网络也是一个流) , 由结论1, $S_f=S_w$. 又由结论2, $f_s$即为$f_{in}$的全部, 所以有$f_s=f_{in}=S_w$, 所以$f_s$为所有流中的最大者.

也可以用反证法. 若存在比Ford-Fulkerson算法得到的流更大的流, 仍然观察上面的点集$S$, 此时从$s$流出的流量$f_{s'}$应当超过了$f_x=S_w$, 这时$S-\{s\}$中的点不可能满足流入每个顶点的流量等于流出的流量, 所以这样的流不存在.

至此, 就证明了Ford-Fulkerson算法的正确性.

模板

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数, 视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge {
ll to, w, rev;
};
vector<edge> G[V];
int s, t;//源点和汇点, 是全局变量
bool vis[V];

ll max_flow();
ll dfs(ll u, ll f);
void add_edge(ll from, ll to, ll w);

ll dfs(ll u, ll f) {
if(vis[u]) return 0;
vis[u] = true;
if(u == t) return f;
for(int i = 0; i < G[u].size(); i++) {
edge &e = G[u][i];//注意是引用, 需要直接修改原图
if(!vis[e.to] && e.w > 0) {
ll curf = dfs(e.to, (f > e.w) ? e.w : f);
//min函数有些编译器不给过
if(curf > 0) {
e.w -= curf;
//直接修改容量而非同时记录f和w, 只是为了方便
G[e.to][e.rev].w += curf;
return curf;
}
}
}
return 0;
}
ll max_flow() {
ll maxf = 0;
while(true) {
memset(vis, 0, sizeof(vis));
ll f = dfs(s, INF);
if(f == 0) break;
maxf += f;
}
return maxf;
}
void add_edge(ll from, ll to, ll w) {
G[from].push_back(edge(to, G[to].size(), w));
G[to].push_back(edge(from, G[from].size() - 1, 0));
}

如有发现模板的错误请联系我指正, 我将不胜感激.