Mengzelev's Blog

问题求解3-总复习

Word count: 4,130 / Reading time: 18 min
2019/01/07 Share

动态规划

最优子结构

  • 问题的最优解由相关子问题的最优解组合而成,这些子问题可以独立求解
  • 使用“剪切-粘贴”技术证明:假设原问题取得最优解时,子问题没有取最优解,那么可以将子结构从整体删除替换为最优解,这与原问题取得最优解的前提矛盾
  • 子问题间互相独立
  • 运行时间:子问题总数*每个问题要考察的选择数

求解时先找出最优子结构,列出递推式

实现

  • 自顶向下的备忘算法(带备忘的递归)
  • 自底向上的动态规划算法(难写,但是快)
  • 并没有板子

能解决的问题

  • 矩阵乘法问题
  • 最长公共子序列
  • 最长上升子序列

>主要就是一个列递推式的问题但是就是列不出来

贪心

贪心选择性质

  • 进行选择时,直接做出当前问题中看来最优的选择,而不必考虑子问题的解
  • 贪心不太方便时可以进行预处理
  • 证明:替换法
    • 贪心算法得到一个解S,假设存在一个抽象的最优解S’,证明S’可以通过若干步满足要求的替换变成S
    • 也可以证明S优于S(e.g.S的代价$\le$S’的代价),加上S’优于S的天然条件,可知S与S’都是最优解

解决问题

  • 教室安排问题
  • Huffman编码树【可以等价为叶结点的带权路径长度之和最小问题
  • 区间选点问题
    • 数轴上有n个闭区间$[a_i,b_i]$。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)
    • 将区间按右端点升序排序,优先处理小区间

实现

  • 这个完全就是因题而异的了啊【哭了

并查集

三个基本操作

  • MAKE-SET($x$)
  • UNION($x,y$)
  • FIND-SET($x$):返回$x$所在集合的代表元

链表

  • 时间复杂度make和find是$O(1)$,UNION$O(n\lg n)$
  • 简单加权合并式启发策略(小的并到大的上

不相交集合森林

  • 按秩合并,路径压缩
  • make和find$O(1)$,UNION$O(m_{\alpha}(n))$

板子

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
void init() {
for(int i = 1; i <= n; ++i) {
f[i] = i;
rank[i] = 0;
}
}

/*递归版*/
int find(int i) {
return f[i] == i ? i : f[i] = find(f[i]);
}

/*非递归版*/
int find(int x) {
int root = f[x];
while(root != f[root]) root = f[root];
int y = f[x];
while(x != root) {
y = f[x];
f[x] = root;
x = y;
}
return root;
}

void unite(int a, int b) {
int fa = find(a);
int fb = find(b);
if(fa != fb) {
if(rank[a] < rank[b]) f[a] = fb;
else f[b] = fa;
}
}

变种

  • 带权并查集
  • 分类并查集

>考到自求多福

解决问题

  • 无向图连通分量个数

图的基本概念

参考了ytr的整理

概念

  • 诱导子图
  • 链walk,迹trail,路path
  • 回路circuit,圈cycle
  • 连通性,连通分支
  • 距离,测地线(长度为$u-v$距离的$u-v$路),直径
  • 环(loop),你 连 你 自 己
  • 平行边:重边
  • 度数deg,最小度数$\delta(G)$,最大度数$\Delta(G)$
  • 度序列,可图的

几种图

  • 完全图$K_n$
  • 补图
  • 二部图,完全二部图($K_{s,t}$),星图star($K_{1,s}$)
  • 多部图,完全多部图(K_{s,s,s})
  • $G+H$:$G$和$H$放一起,顶点两两连起来
  • $G\times H$:$G$的每个点都替换成一个$H$
  • n方体cube($Q_n=Q_{n-1}\times K_2$)
  • $r-$正则图:每个点度数都为$r$

定理

  • 设$G$是一个阶至少为3的图,则$G$是连通的当且仅当$G$包含两个不同的顶点$u$和$v$,使得$G-u$和$G-v$都是连
    通的
  • 非平凡图$G$是二部的当且仅当$G$不含奇圈
  • 图论第一定理:度数和=边数*2
  • 每一个图都有偶数个奇点
  • 设$G$为$n$阶图,若对于$G$中任意两个不邻接的顶点$u$和$v$, 都满足$$deg~u+deg~v\geq n-1$$,则$G$是连通的且$diam(G)\leq$2
  • 设$r$和$n$为满足$0\leq r\leq n-1$的整数. 则存在n阶的r正则图当且仅当$r$和$n$中至少有一个为偶数
  • 度序列可图的充要条件(删掉一个点依然可图)

定义

  • 割边
  • 树,森林

定理

  • 某条边是割边当且仅当该边不在任何一个cycle上
  • 每一棵非平凡树都至少有两个端点(最长路径的两个端点)
    • 【可以成为数学归纳法的依据】
    • 使用数学归纳法证明图论问题的关键在于找到一个端点
  • 有$k$个连通分量的森林有$n-k$条边,树就有$n-1$条边
  • 每一个有$n$个顶点的连通图至少有$n-1$条边【证明:最小数原理】
  • 任意两条可得树:连通、无环、$m=n-1$
  • 每个连通图都包含一棵生成树
  • Matrix Tree Theorem:连通图$G$的生成树个数可以用行列式求得
  • $T$是唯一最小生成树当且仅当$\forall e\in G\setminus T: w(e)>w(\text{every other edge on the cycle in $T+e$})$
    • 推论:distinct weights $\Leftarrow$ unique MST
    • 推论:Maximum-weight edge in any cycle is unique $\Leftarrow$ unique MST
  • 若每个点度数大于等于2,则该图有cycle
  • $e$是割边当且仅当$e$存在于$G$的某一棵生成树上

最小生成树性质

  • Cut Property
    • VER I:$X$是某棵最小生成树的一部分,$(S,V\setminus S)$是一个$X$没有横跨的切割,$e$为横跨$(S,V\setminus)$的一条最轻的边,则$X\cup {e}$是某棵最小生成树$T_2$的一部分。
    • VER II:$e$为横跨$(S,V\setminus)$的一条最轻的边,则$e$属于某棵最小生成树
    • 贪心选择性质,可由替换法证明
  • Cycle Property
    • 若$e$为任意一个cycle上权重最大的一条边,则存在一棵最小生成树$T$,使$e\notin T$

Kruskal

  • $O(E\lg~V)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int kruskal() {
sort(edge, edge + m, cmp);//将边按权重从小到大排序
int cnt = 0;
int ans = 0;
for(int i = 1; i <= n; ++i) f[i] = i;//初始化并查集
for(int i = 0; i < m; ++i) {
int a = edge[i].u;
int b = edge[i].v;
int fa = find(a), fb = find(b);
if(fa != fb) {
f[fa] = fb;
ans += edge[i].w;
cnt ++;
if(cnt == n - 1) break;
}
}
return ans;
}

Prim

  • $O(E\lg V)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int my_prim() {
int ans = 0;
for(int i = 0; i < n; ++i) {
mincost[i] = INF;
vis[i] = false;
}
while(true){
int v = -1;
for(int i = 0; i < n; ++i) {
if(!vis[i] && (v == -1 || mincost[i] < mincost[v])) v = i;
}
if(v == -1) break;
vis[v] = true;
ans += mincost[v];
for(int i = 0; i < n; ++i) {
mincost[i] = min(mincost[i], map[v][i]);
}
}
return ans;
}

图的计算机表示及其遍历

图的表示

  • 邻接链表
  • 邻接矩阵

BFS

  • 维护一个队列
  • 时间复杂度$O(V+E)$
  • 搜完了会得到广度优先树

DFS

  • 前驱子图:深度优先森林
  • 边的类型
    • 树边
    • 前向边F:祖宗指向儿子
    • 后向边B:儿子指向祖宗
    • 横向边C:没有亲缘关系
  • 复杂度$O(V+E)$
  • 每个结点有两个时间戳
    • $v.d$:记录该结点第一次被发现的时间
    • $v.f$:记录搜索完成对$v$的邻接链表的扫描的时间
    • $v.d<v.f$

拓扑排序

  • 根据DFS后的$v.f$时间戳降序排序,即拓扑序最前的最晚结束访问
  • 若$(u,v)\in G$,则$v.f<u.f$
  • 只有DAG才有拓扑排序

SCC

算法描述

  • DFS($G$)
  • DFS($G^{T})$,在主循环根据$v.f$的大小降序访问其邻接点,得到的每棵树都是一个强连通分量

单源最短路径

  • 松弛操作唯一导致最短路径估计和前驱结点发生变化的操作

性质

  • 三角不等式性质:$s,u,v$
  • 上界性质:$v.d$撑死就是$\delta(s,v)$
  • 非路径性质:$s-v$之间没路则$\delta(s,v)=+\infty$
  • 收敛性质:松弛前是最短路径,松弛后也是最短路径
  • 路径松弛性质:一条最短路径上的点按先后顺序松弛,则终点的估计值等于最短路径长度
  • 前驱子图性质:$v.d=\delta(s,v)$,则前驱子图是一棵根结点为$s$的最短路径树

Bellman-Ford

  • 对每条边进行$|V|-1$次relax
  • 可以识别负权重环
  • $O(VE)$
  • 本质上是DP
1
2
3
4
5
6
7
8
9
10
11
12
13
void bellman_ford() {
dist[s] = 0;
for(int i = 1; i <= n - 1; ++i) {
for(int j = 1; j <= m; ++j) {
if(dist[e[j].u < INF && dist[e[j].v] > dist[e[j].u] + e[j].w) {
dist[e[j].v] = dist[e[j].u] + e[j].w;
pre[e[j].v] = e[j].u;
}
}
}
for(int j = 1; j <= m; ++j)
if(dist[e[j].v] > dist[e[j].u] + e[j].w) flag = false;
}

DAG

  • 按拓扑序松弛结点(路径松弛性质保证)
  • $\Theta(V+E)$

Dijkstra

  • 所有权重都非负
  • 二叉堆实现$O(E\lg V)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dijkstra() {
prority_queue <node> q;
ver[0].d = 0;
q.push(ver[0]);

while(!q.empty()) {
node u = q.top();
q.pop();
for(int i = 0 ; i < son[u].size(); ++i) {
int vid = son[u.id][i];
if(ver[vid].d < u.d) continue;
if(ver[vid].d > u.d + map[u.id][vid]) {
ver[vid].d = u.d + map[u.id][vid];
q.push(ver[vid]);
}
}
}
}

差分约束

  • 差分图:若$x_j-x_i\le b_k$,则$w(v_i,v_j)=b_k$
  • Bellman-Ford可以求解

所有结点对最短路

矩阵乘法

  • 我不想管了!!
  • 是$n$维的Bellman-Ford

Floyd-Warshall

  • 本质DP,枚举最短路径上的中间结点
  • 不允许负权重环,但是能报错(看对角元是否有负数)
  • $\Theta(n^3)$
1
2
3
4
5
6
7
void floyd() {
init(); //记得将所有map[i][i]置零
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}

Johnson算法

  • 用于稀疏图
  • 重新赋值
    • 新增源点$s$,该点与各点有权重为0的边
    • 先跑一次Bellman-Ford,没有负权重环就重新赋值为$\hat{w}(u,v)=w(u,v)+\delta(s,u)-\delta(s,v)$
    • 对每个点Dijkstra
    • 恢复权重并返回
  • $O(VE\lg E)$

连通度

割点

  • $v$与割边相连,则$v$是割点当且仅当$deg~v\ge 2$
  • 对于至少有3个顶点的连通图,只要有割边,就一定有割点
  • $v$是连通图$G$的割点,当且仅当存在两个不同的顶点$u$和$w$,使得$v$位于$u-w$的任意一条路径上
  • 非平凡连通图中,距离某个点最远的点不是割点
  • 任意非平凡连通图至少包含两个非割点的顶点
  • 不可分图:没有割点的非平凡连通图

  • 图的一个最大不可分子图【类比连通分量
  • 任意两个不同块的性质
    • 不相交
    • 至多一个公共点
    • 如果有公共点,则该公共点为割点

连通度

  • $\kappa(G)$点连通度=最小顶点割基数
  • $\lambda(G)$边连通度=最小边割基数
  • 点连通度$\le$边连通度$\le$最小度数
    • $\kappa(G)\le \lfloor\frac{2m}{n}\rfloor$

Menger定理

  • 设$u$和$v$是$G$中两个不邻接的顶点,则$u-v$的最小分离集的顶点个数等于内部不相交$u-v$路的最大个数
  • 类似的有边定理:分离$u-v$的边的最小个数等于边不相交$u-v$路的最大个数

  • $k$连通当且仅当任意两个顶点至少有$k$条内部不相交路

  • $k$连通图中任意$k$个顶点均位于某一个圈上

Tarjan算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*无向图tarjan*/
void tarjan(int u, int pre) {
int child = 0;
dfs_clock ++;
dfn[u] = low[u] = dfs_clock;
for(int i = 0; i < son[u].size(); ++i) {
int v = son[u][i];
if(!dfn[v]) {//(u,v)是树边
tarjan(v,u);
child ++;
low[u] = min(low[u], low[v]);
if((u == 1 && child > 1) || (u != 1 && dfn[u] <= low[v])) {
cut_node.push_back(u);
}//割点判定:根结点有多个子树,或非根结点的访问序数小于等于能回溯的最大祖先
if(low[v] > dfn[u]) bridge.push_back({min(u,v), max(u,v)});
}
else if(dfn[v] < dfn[u] && v != pre) low[u] = min(low[u], dfn[v]);
}
}

旅行问题

欧拉图

  • 欧拉回路【闭合】/欧拉迹
  • 有欧拉回路才算欧拉图
  • 一个非平凡连通图是Euler的 当且仅当它的每个顶点的度都为偶数
  • 有欧拉迹当且仅当只有两个奇度点

哈密尔顿图

  • 哈密尔顿圈/哈密尔顿路
  • 性质
    • $G$的任一非空子集$S$,都有$k(G-S)\ge |S|$($G$是哈密尔顿图,$k(G)$指图$G$的连通分支数)
  • 充分条件
    • (Ore定理)对于不少于3个顶点的图,任意两个不邻接的顶点度数之和大于等于$n$,则$G$是哈密尔顿的。
    • 推论:每个点的度数大于等于$n/2$
    • $u$和$v$是不邻接的两个顶点,且度数之和大于等于$n$,则$G+uv$是哈密尔顿的当且仅当$G$是哈密尔顿的
    • 一个图是哈密尔顿的当且仅当它的闭包是哈密尔顿的
    • 对于每个整数$j(1\le j\le n/2)$,$G$中度数至多为$j$的顶点数小于$j$,则$G$是哈密尔顿的

匹配与覆盖

匹配

  • Hall条件:$\forall X\subseteq U, |N(X)\ge |X|$
  • 婚姻定理:$r$个女人,$s$个男人,可能出现$r$对婚姻当且仅当对任意$k$,任意$k$个女人共认识至少$k$个男人。
  • 最大匹配
  • 完美匹配:阶为$2k$的图存在一个基数为$k$的匹配
  • 任意$r$正则二部图均有一个完美匹配

独立性参数

  • 最大边独立数$\alpha’(G)$
  • 最下边覆盖数$\beta’(G)$
  • 最大点独立数$\alpha’(G)$
  • 最小点覆盖数$\beta(G)$
  • Gallai恒等式
    • 点独立数+点覆盖数=$n$
    • 边独立数+边覆盖数=$n$
  • 一般独立集比覆盖集好求

因子分解

  • $r-$因子:图$G$的$r-$正则生成图
  • 完美匹配产生1-因子
  • 图$G$包含1-因子当且仅当对于$V(G)$的任意真子集$S$,$k_O(G-S)\le |S|$。($k_O(G)$表示$G$的奇连通分支个数)
  • Petersen定理:所有无割边的3-正则图包含1-因子
  • 任一至多有两条割边的3-正则图包含1-因子
  • 可因子分解:能划分成多个因子
  • Petersen图不可1-因子分解

匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool find(int x) {
for(int i = 1; i <= n; ++i) {
if(map[x][i] && !vis[i]) {
vis[i] = true;
if(match[i] == 0 || find(match[i])) {
match[i] = x;
return true;
}
}
}
return false;
}

int hungary() {
int ans = 0;
for(int i = 1; i <= n; ++i) {
memset(vis, 0 ,sizeof(vis));
if(find(i)) ans ++;
}
return ans;
}

最大流

  • $f:V\times V\to\mathbb{R}$
  • 容量限制:$0\le f(u,v)\le c(u,v)$
  • 流量守恒:$\forall u\in V-s,t, \sum\limits_{v\in V}f(u,v)=\sum_\limits_{v\in V}f(v,u)$【流入=流出】
  • 流的值$|f|=\sum\limits_{v\in V}f(s,v)-\sum\limits_{v\in V}f(v,s)$(从源结点流出的总流量-流入源结点的总流量)

几种特殊处理

  • 反平行边:拆其中一条边为两条边
  • 多源多汇

残存网络

残存容量
$$c_f=(u,v)=\begin{cases}
c(u,v)-f(u,v) & (u,v)\in E \
f(v,u) & (v,u)\in E\
0 & o.w.$$

切割

  • 把$V$划分为$S$和$T$两个集合,其中$s\in S, t\in T$
  • 横跨该切割的净流量:$f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)-\sum\limits_{u\in S}\sum\limits_{v\in T}f(v,u)$【所有结点对的流量之和
  • 切割的容量:$c(S,T)=\sum\limits_{v\in S}\sum\limits_{v\in T}c(u,v)$【只考虑$S$出发进入$T$的容量
  • 最小切割:容量最小的切割
  • 最大流最小割定理

网络流解决最大匹配

  • 一个集合连$s$,一个集合连$t$,两个集合间两两连,每条边都是单位容量
  • $O(VE)$

图论证明方法

解题时可能会用到一个或多个

  • 反证法
  • 构造法
  • 临界法(最小/最大的满足条件的一个图)
  • 归纳法
  • 算两次
CATALOG
  1. 1. 动态规划
    1. 1.1. 最优子结构
    2. 1.2. 实现
    3. 1.3. 能解决的问题
  2. 2. 贪心
    1. 2.1. 贪心选择性质
    2. 2.2. 解决问题
    3. 2.3. 实现
  3. 3. 并查集
    1. 3.1. 三个基本操作
    2. 3.2. 链表
    3. 3.3. 不相交集合森林
    4. 3.4. 板子
    5. 3.5. 变种
    6. 3.6. 解决问题
  4. 4. 图的基本概念
    1. 4.1. 概念
    2. 4.2. 几种图
    3. 4.3. 定理
  5. 5.
    1. 5.1. 定义
    2. 5.2. 定理
    3. 5.3. 最小生成树性质
    4. 5.4. Kruskal
    5. 5.5. Prim
  6. 6. 图的计算机表示及其遍历
  7. 7. 图的表示
    1. 7.1. BFS
    2. 7.2. DFS
    3. 7.3. 拓扑排序
    4. 7.4. SCC
  8. 8. 单源最短路径
    1. 8.1. 性质
    2. 8.2. Bellman-Ford
    3. 8.3. DAG
    4. 8.4. Dijkstra
    5. 8.5. 差分约束
  9. 9. 所有结点对最短路
    1. 9.1. 矩阵乘法
    2. 9.2. Floyd-Warshall
    3. 9.3. Johnson算法
  10. 10. 连通度
    1. 10.1. 割点
    2. 10.2.
    3. 10.3. 连通度
    4. 10.4. Menger定理
    5. 10.5. Tarjan算法
  11. 11. 旅行问题
    1. 11.1. 欧拉图
    2. 11.2. 哈密尔顿图
  12. 12. 匹配与覆盖
    1. 12.1. 匹配
    2. 12.2. 独立性参数
    3. 12.3. 因子分解
    4. 12.4. 匈牙利算法
  13. 13. 最大流
    1. 13.1.
    2. 13.2. 几种特殊处理
    3. 13.3. 残存网络
    4. 13.4. 切割
    5. 13.5. 网络流解决最大匹配
  14. 14. 图论证明方法