给中级者的动态规划教程

认识更多模型

区间DP

POJ 2955 Brackets:最简单的区间DP,括号序列

LA4394 String Painter:两层区间DP,难度较大

概率DP

POJ 3744 Scout YYF I:概率型递推配合矩阵快速幂加速

POJ 2096 Collecting Bugs:优惠券问题的二维情形

状态压缩DP

UVA 10911 Forming Quiz Teams:最优配对问题

LA3725 Hie with the Pie:TSP问题

树DP

POJ 1655 Balancing Act:求树的重心

Codeforces 461B Appleman and Tree:最大独立集问题的变种

 

 

位运算有关小技巧

基本运算

以下a指一个二进制位。

NOT

  • ~1 = 0
  • ~0 = 1

如果智商正常应该不会不能理解取反运算吧

AND

  • 1&a = a
  • 0&a=0

由此可见善加利用AND运算,可以保证某个二进制数的特定位为0,其余的位保持原样。

OR

  • 1|a=1
  • 0|a=0

由此可见善加利用OR运算,可以保证某个二进制数特定位为1,其余位维持原样。

XOR

XOR/异或运算具有重要性质:

  • a^a = 0
    XOR可以代替等于
  • 0^a = a
    0是XOR运算的单位元
  • 1^1=0 1^0=1
    用1去做XOR运算可以实现“开关”某个二进制位的效果
  • abs(a^1-a)=1
    用1对一个数去做XOR可以实现求与这个数相邻的数的效果
    比如2^1=3 3^1=2
  • 1^1 = 0;1^1^1 = 1;1^1^1^1 = 0
    XOR与奇偶性紧密相连

SHL/SHR

左移运算相当于除以2,右移运算相当于乘2.

运算技巧

scanf

while(~scanf(” %d”,&n)){}
while(scanf(” %d”,&n) != EOF){}

两种形式等价

判断奇偶性

if a&1 == 1 then a is odd
if a&1 == 0 then a is even

取出最低位

lowbit(x) = x&(-x)

制作全1掩码

mask = (1 << n) – 1

理论最大最小值

INTMAX = ~(1 << 31)
LLMAX = ~(1ll << 63)

INTMIN = 1 << 31
LLMIN = 1ll << 63

常用最大值

memset(dp,0x3f,sizeof(dp))

装逼

swap

a= a ^ b
b = a ^ b
a = a ^ b

绝对值

abs(n) = (n ^ (n >> 31)) – (n >> 31)

最大值

max(a,b) = b & ((a-b) >> 31) | a & (~(a-b) >> 31)

最小值

min(a,b) = a & ((a-b) >> 31) | b & (~(a-b) >> 31)

集合

表示集合

用二进制位表示集合是很简单也是很直观的,直接举个例子:假设全集是{a,b,c,d,e,f,g,h},这样我们一共有8种不同的元素,怎么表示{a,c,e}这个集合呢,很简单,我们拿出8个二进制位,从左到右分别表示“a,b,c,d,e,f,g,h”,那么{a,c,e}就可以用二进制”10101000″ 表示。

操作用二进制表示的集合

加入元素:使用“或等”运算

删除元素:使用“和等”运算

确认元素是否在内:使用“和”运算

并集:使用“或”运算

交集:使用“和”运算

补集:先使用“取反”运算,再使用“和”运算

开关:使用“异或”运算

枚举

枚举全部的集合形态:从0枚举至11111111…

枚举某个集合的自己:-1,然后和求子集的集合做“和等”

图论

获取反向边

i i^1互为反向边,要求插边时必须同时插入正边和反边,边数组编号从2的倍数或0开始。

数据结构

二叉树

令根节点为1

编号x的节点的左儿子编号: (x << 1)
编号x的节点的右儿子编号: (x << 1) + 1
编号x的节点的父亲编号: (x >> 1)
编号x的节点的兄弟编号: (x ^ 1)

二叉树两个节点节点是否相邻

使用堆存储,根节点编号为1,如果a^b=1,则两个点必定同属一个父亲

二叉堆

先坑着,看需求

动态规划

滚动数组

模运算很慢,所以我们用XOR代替mod2。

int tick = 0;
for(){
dp[tick^1] = dp[tick];
tick ^= 1;
}

快速幂

这里暂时不详细提供代码了。

 

动态规划初步

[toc]

什么是动态规划

  • 动态规划是一种方法,或者说思想,它并不是某种特定算法。
  • 动态规划方法的通俗解释:将原来比较复杂的问题分解为若干比较简单的子问题,将这些子问题逐个解决,并存储这些子问题的答案,原来的问题的答案将会从这些分解了的子问题的答案中导出。等到下一次遇到了相同的子问题时,我们只是提取出事前存储的问题的答案,而不是重新做一次计算。
  • 对上面通俗解释的解释:无论是原问题,还是子问题,都是问题,我们拿到一个问题,给他分解为若干子问题,那么接下来我们如何解决子问题?那就是把每个子问题当成原问题再度分解,得到子问题的子问题,然后为了解决这些“子问题的子问题”,我们再度分解。。。直到最终我们得到了已经无法再分的“原子问题”,我们假定原子问题是可以很好地被解决的,那么我们理论上只要解决的全部的原子问题,再回推,就可以解决掉全部子问题,最终解决最根本的问题,也就是我们拿到的问题。而动态规划方法体现在我们加速这个过程上,在问题的分解过程中,我们可能会遇到重复的情况,如果我们对这些重复的情况调用之前计算好的答案,就不用再次深入分解问题,这样能大大加快整个求解进程。
  • 动态规划的关键字:递推、记忆化、状态转移

状态

什么是状态

  • 字面含义:物质系统所处的状况。
  • 我们这里所说的状态是一种抽象观念。
  • 在动态规划的设计上,一个“状态”,表达的是在某个情形下的子问题。
  • 在动态规划的操作上,状态最终表现为一个又一个的值,也就是在某个特定情形下的子问题的答案。

状态转移

  • 基于当前状态和其他输入,移动到其他状态。
  • 说人话:某个东西现在是某个样子的,然后我对他动了些手脚,这个东西变成了另外一幅样子。
  • 当前状态能不能转移到当前状态?可以
  • 如何表达状态转移?
    • 状态转移方程(你可以列个公式)
    • 状态转移图(你可以把状态形象化为点,把转移条件形象化为边)
    • 状态转移表(你听说过函数表吗?虽然没怎么用过但这是初中内容。)

那么状态和动态规划有什么关系?

上面说到了,在动态规划里的“状态”表达的是“子问题”,前面也说了,动态规划整体来看是一个操作子问题的方法,这样我们也可以说动态规划是一个操作状态的方法。在动态规划过程中,我们分解当前状态,得到子状态,处理子状态,记忆子状态,最终处理好全部需要处理的状态,从所有状态中挑出合适的、我们需要的状态来代表最终答案。

用动态规划解决问题

必要条件

不是所有的问题都能用动态规划解决,能够使用动态规划方法解决的问题必须满足以下两个基本性质:

  • 对于一个问题,如果它取得了最优解,那么这个问题所能分解出来的所有子问题的解也是最优的,这个性质称为最优子问题/最优子结构
  • 如果我们已经解决了一些问题,那么当我们解决其他问题的时候,已经解决的问题的答案必须不能受新解决的问题影响。也就是说某个状态之后的过程不可以影响之前的状态。这一性质,称为无后效性

分治?

聪明的你发现了,分治法不也是把当前问题分解为小一点的问题直到不能再分,然后解决原子问题回推得到根问题的答案吗?分治和动态规划有什么区别?

适用于用动态规划法求解的问题,分解后的子问题往往不是独立的,在之后的求解过程中会用到之前已经解决的问题的答案。

上面说过了,动态规划过程中每个子问题的答案将会被保存以避免重复计算,这里才是我们高速解决问题的原因。因此我们有下面这种说法:

使用动态规划有意义的条件

  • 子问题之间不是独立的,一个子问题在之后的求解过程中可能会被多次使用到。这个性质称为重叠子问题
  • 需要注意重叠子问题并不是动态规划适用的必要条件,但是如果没有这个性质,使用动态规划并没有意义。

操作步骤

我们使用动态规划方法解决问题时,一般按照以下思维和操作程序:

  • 分析问题:判定其是否能且有意义使用动态规划。
  • 再度分析:找出将问题分解的方法,将分解后的问题合并的方法,确定原子问题的位置(即边界条件)。
  • 定义状态:确定每个状态对应的问题是什么,答案表示什么,携带的情形是什么。
  • 处理状态:递推 and/or 记忆化。
  • 选择答案:从处理好的状态中选择我们需要的合适的状态作出最终答案。

关键点

  • 状态设计
  • 转移方程
  • 初始化
  • 二次优化(本文不讨论)

如果把目光放长远一点

  • 动态规划方法解决了一个问题,但这很可能并不是你要解决的问题的全部。
  • 递推可以叫动态规划吗?我认为可以,你可以看成每个问题只能分解出一个子问题,虽然感觉上有一点奇怪,而且你要注意到递推过程中并没有重叠子问题,即使你管他叫动态规划,那也是没啥意义的动态规划。
  • 开一下脑洞:你用一种动态规划方法分解出来的原子问题需要另外一种动态规划方法解决?你现在动态规划解决的问题其实只是另一个问题的模块?想想就好了,高中生啥都干的出来。

一些经典且简单的模型

关于Fibonacci

广义/系数Fibonacci

首先要说的是,Fibonacci数列中,最有分量的一句话其实是f_i = f_{i-1} + f_{i-2}f_1f_2的值并不重要,所以我们在这里可以推广Fibonacci数列的含义为只要有这样的递推就可以称为(广义)Fibonacci数列。

我们都知道Fibonacci数列,要想快速应付多次查询我们可以事前预处理,要想快速应付一次巨大的查询我们可以使用矩阵快速幂。那么如果我给出下面的问题呢?

Given f_1 = a,f_2 = b,f_i = f_{i-1} + f_{i-2} for every f >= 3,for each query you will get 3 numbers a,b,c,you have to output f_c in condition of given a and b.

这个问题意外的简单,仔细观察我们就发现了,对于给出的这个数列的每一项,a的系数实际上是f_1=1,f_2=0的Fibonacci数列,b的系数实际上是f_1=0,f_2=1的Fibonacci数列,所以接下来怎么操作想必大家都很清楚。

Fibonacci的前缀和?

是的,也是Fibonacci数列。

前两项的作用

前两项事实上决定了整个Fibonacci数列,因此只要知道前两项,就相当于知道了整个Fibonacci数列。

数字三角形

问题

POJ 1163 The Triangle

解法

我们令A[i][j]表示金字塔从上往下数第i行第j个数。

我们令dp[i][j]表示从金字塔从上往下数第i行第j个数。

对于金字塔上每一个点,我们假定已经计算出了从这个点左下方出发走完金字塔的最优解和右下方走完金字塔的最优解,那么从这个点走完金子塔的最优解已经是从左下方或右下方走完这两个可能性中最优的那个,再加上当前这个点的数值,即:

dp[i][j] = best(dp[i+1][j],dp[i+1][j+1]) + A[i][j]

对于最后一行,因为已经是底部,所以dp[i][j] = A[i][j]

最后,我们需要的答案是从塔尖走完整个金字塔的最优解,即dp[1][1]。

问题解决。

背包问题

背包问题九讲

我们只关心这些内容:

  • 01背包
  • 完全背包
  • 多重背包
  • 滚动数组

最长上升子序列

问题

POJ 2533 Longest Ordered Subsequence

解法

令A[i]表示原数列第i位数。

令dp[i]表示检查到原数列第i位(且最后一位就是第i位)时的最长公共子序列长度。

那么对于没有解决的dp[i],我们依次检查所有在第j位之前的数,假设检查到了第j位:

  • 如果A[j] < A[i],那么我们可以选择在j位表示的最长上升子序列后面添附第i位数,这样得到了一种可能的dp[i]=dp[j]+1
  • 否则,我们只能选择放弃之前的结果,这样得到了一种可能的dp[i]=1
  • 我们综合所有可能的dp[i],选出最大的那个,保存

对于第1位,显然只有它自己一个构成了一个上升序列,因此dp[1] = 1。

这样我们完成了状态转移,最终结果就是dp数组中的最大值.

我们只关心O(n^2)的解法(还有一种O(nlogn)的解法)。

数学相关算法小总结

HDU5446

正确的拆乘防爆,超大素数取模,Lucas定理,CRT合并。

 

(Extended) Baby Step Giant Step Algorithm

用于求出满足A^x=B(mod C)的最小的x。

  • 参数配置:
    • HASHMOD:Hashtable的Hash空间大小,爆内存要改小
  • 调用方法:exBSGS(A,B,C);

指数循环节

若A^start = B (mod P)求出最小的len使得A^(k*len) = B (mod P),原理是这种对于一个值的循环节长度一定是Phi(P)的约数,所以不断约掉因子并尝试。

 

字符串算法小总结

Extended Knuth-Morris-Pratt Algorithm

模板

  • 参数调整:MAXN是字符串的理论最大长度
  • 调用:exKMP_getextend(char* 母串,char* 模式串),会同时处理好next数组和extend数组,数据间无需初始化。
  • exKMP_next[i]表示模式串mode[i~(len-1)]与整个模式串的最长公共前缀长度
  • exKMP_extend[i]表示母串str[i~(len-1)]于整个模式串的最长公共前缀长度

题目

HDU 4300 Clairewd’s message

Aho-Corasick Automaton

模板

  • 参数调整:
    • SP:字符集大小
    • MAXN:理论上Tire树的节点上限
    • mark():用来将字符映射到SP规定的字符集大小内的函数
    • ACA_match():需要按照题目要求更改匹配时行为
  • 调用:
    • 初始化:init()
    • 插入模式串:insert()
    • 构建fail指针:ACA_buildfail()
    • 匹配母串:ACA_match()
  • 活用注记:
    • root表示没有匹配到任何字符,如果超出字符集,也要转移到root
    • 每一个节点的fail指针对应节点是等价的更早状态(包括root状态)
    • 每个节点指向失配的出边实际上指向的是其fail指针对应状态中对应出边指向的状态

题目

[Pending]

Suffix Automaton

模板1~指针实现,动态分配内存

模板2~数组实现,支持删除后缀

 

欧拉图和哈密顿图小总结

欧拉图

概念

定义

欧拉回路:图中经过每条边一次且仅一次的环;
欧拉路径:图中经过每条边一次且仅一次的路径;
欧拉图:有至少一个欧拉回路的图;
半欧拉图:没有欧拉环,但有至少一条欧拉路径的图。

无向图判定条件

  • 图是联通的(度数为0的点不用考虑,因为是孤立的点,没影响)~先决条件
  • 所有点的度数都是偶数~存在欧拉回路,欧拉图
  • 有且仅有两个点的度数是奇数~存在欧拉路径,半欧拉图
    两个奇数度数的点一个是路径起点一个是路径终点

证明:因为任意一个点,欧拉环(或欧拉路径)从它这里进去多少次就要出来多少次,故(进去的次数+出来的次数)为偶数,又因为(进去的次数+出来的次数)=该点的度数(根据定义),所以该点的度数为偶数。

有向图判定条件

  • 把所有的边强行改为无向边之后(这个图叫原图的基图),联通~先决条件
  • 所有点出度等于入度~存在欧拉回路,欧拉图
  • 有且仅有两个点出度不等于入度,一个出度比入度大1,另一个入度比出度大1~欧拉路径,半欧拉图
    出度比入度大1的点是路径起点,入度比出度大1的点是路径终点

证明:与无向图证明类似,一个点进去多少次就要出来多少次。

模板

 

初步认识图和暴力搜索

[toc]
图(Graph)作为一种非常常见且有效的模型和抽象手段,不仅是在竞赛中,乃至整个CS的学习和应用过程中都有着举足轻重的地位,尽早掌握一些关于图的概念也能辅助我们更好地分析手边的问题。本文介绍一些关于图的最基本概念和实际应用上的一些基本技术。

图的基本知识

在这里我给出这样一个问题:你站在1上,1能走到3,1能走到2也能从2走回来,7能走到5也能从5走回来,7能走到6也能从6走回来,2和5和6互相连通,1自己能走到自己,3能走到4.那么你都能走到那些点呢?

你可能很自然的会想到把我上面说的那一坨给画成一个“路线图”或“地图”,这样只要一看这个图就可以一目了然了,而接下来要说的计算机/数学中的“图”就是这样的一种抽象方式。

来和“图”桑见一面

图的定义很简单,给你几个圆,再把圆和圆之间拿线连起来,就可以称为图了。

定义: 由若干个不同的顶点与连接其中某些顶点的边组成的图形称为图。

g01
An Example of Graph

上面这个就是一个典型的图了,这个图反映的就是我上文中说的那些关系,图里绿色的圆,称为“节点/顶点(Node/Vertex)“,为了接下来叙述的方便,我给每一个节点都挂上了一个编号,在实际应用中,节点上能够挂载任何你需要的信息。圆与圆之间连接着的线,不管长成什么样,都称为“边(Edge)”,边上面也可以挂载信息。

我们发现了,上图中边中,有的是拿直线段表示的,这种边称为“无向边”,比如上面图中的2号点和5号点的连边,这样的边表示“一端(2号点)和另外一端(5号点)可以经由此边互相到达”。‘

而3号点和4号点之间的连边上面有一个箭头,方向是3号到4号,这样的边称为“有向边”,含义是“你只能从一端(3号)经由此边到达另一端(4号),但是并不能反过来”。这样看来,其实无向边可以看成两条方向互反的有向边,这一条性质非常有用。

有的时候,在两个节点之间,可能有着多条无向边或者是相同方向的有向边,这种情况,称为“重边”。

然后再看1号点,我们发现他自己居然和自己连了一条边,这样的边称为“自环”。

而看一下2号、5号、6号和7号,我们发现这四个节点,和他们之间的边共同组成了一个“环”,如果我们以一个方向沿着环行走,恐怕是一辈子也出不去了-_-#。组成环的边可以是无向的,也可以是有向的,沿着一系列的有向边行走,最后走回到了起点,这些有向边就组成了“有向环”。

给图挂载信息

我们先假设这样一种问题情境:你自驾去了一个旅游区,现在正在景区门口盘算着旅游的路线,你知道景区里面没办法加油,所以你已经加满油了,你的油箱容量是K个单位,现在给了你景区的平面图,上面记载了两个景点之间连接着的最近道路的距离(已经被折算成了通过一次要消耗的油量)和你来景区之前调查好的每一个景点的美丽程度。你需要设计一种路线,使得可以用有限的K个单位的燃料,游玩的景点的美丽程度之和最大(你不用考虑游玩结束没油怎么回景区的问题,因为你的保险公司提供免费的拖车服务)。

这个问题就是图论派上用场的时候了,我在这里随便举了一组实例:

g02

 

景区大门和每一个景点,都可以抽象为图上的一个顶点,而每一条道路都可以抽象为图上的一条边。

我们知道每一个景点都有一个“美丽程度”,这个美丽程度就体现在上面这个图里面每一个节点里填着的数字,我们把这种称为“点权”。

每一条道路,都有一个“耗油量”,体现在图上就是边上的数字就是“边权”。

所谓“权(Weight)”,其实就是一种定量的评价标准,怎么样理解附挂在图上的权,是我们自己决定的。

而图上附挂的信息又不仅仅是权值,理论上我们可以给图的任何部分挂载任何我们想要的信息,试想一下,如果我们给每一个节点挂载一个列表,上边记载了从这个可以到达的全部节点的编号,会怎么样?如果我们给每一条边挂载一个数对,上面记载了边的两端所连接的节点的序号,会怎么样?

而接下来要讲的“图的存储”,其实就是几种“挂载信息”的方式。

图的常见存储方式

计算机是不长眼睛的,你也不可能指望它看到上面我们画出来的圆和线就能解决问题。因此我们要把手中的图通过一种计算机可以理解的方式进行转化并存储才行。

常见的存储方式有四种:“邻接矩阵”、“邻接表”、“前向星”、“链式前向星”。他们各有各的特点,其中“前向星”和“链式前向星”其实是邻接表的实现方式,这两种里面我们只需要学习“链式前向星”就可以了。

邻接矩阵

首先,为了方便起见,我们要把图中每一个节点都编号,在这里我们编号1~n。接下来创建一个n*n的全是0的矩阵(或者其他你设定的用来表示无法联通的值),然后我们挨个处理图中的每一条边,对于一条有向边,从a号点指向b号点,那么我们就把矩阵的a行b列修改为1,表示从a到b可以通过。对于一条无向边,连通着a号点和b号点,那么我们就把矩阵的a行b列、b行a列都修改为1,因为无向边可以看成两条方向互反的有向边。

如果你想给边挂边权,怎么办?很简单,矩阵的数值就可以当成边权来用,不过如果你的权值和矩阵中你设定的标记冲突,你就要单独开一个数组来记录了。

如果你想给点挂点权,也需要单独开一个数组来记录。

邻接矩阵的特点是查询一个点到另外一个点之间是否有边和这条边的信息,O(1)就可以查到。但是如果我们要询问一个点连出/连入的所有边(也就是所谓的“遍历”),就必须要检查邻接矩阵的一整行/一整列,这样复杂度就是O(n)。同时,因为是使用数组保存,如果图里有重边,你最终只能保存最后保存的那一条边,也就是会丢失信息,因此一旦有无法忽略的重边,就一定不可以使用邻接矩阵。

看到这里你可能觉得邻接矩阵有点傻,那你可就错了。求多源最短路的Floyd-Warshall算法,求传递闭包的Floyd-Warshall算法,有限状态自动机的状态转移方法数等等都是要使用邻接矩阵的。

邻接表(STL vector实现)

还记得上文的“如果我们给每一个节点挂载一个列表,上边记载了从这个可以到达的全部节点的编号,会怎么样”吗?其实这就是邻接表的一种实现方式。

我们依然要给每一个节点编号,不过这时更多的是为了方便了(如果不编号,就可能要借助指针)。对于每一个点,我们给它挂上一个vector,在这里我给他起名叫to。然后我们还是挨个处理原图中的每一条边。对于一条从a到b的有向边,我们只要对a中的to.push_back(b)就可以了。对于无向边,因为无向边可以看成两条方向互反的有向边,所以就是a.to.push_back(b)和b.to.push_back(a)两步。

在这里我用了个结构体,这是为了方便我们挂载信息的。如果我们想挂点权,直接在Node里面多来一个int什么的就好,如果想挂边权,就再来一个vector,与to同步push_back对应边的权值。

邻接表非常常用,首先他是以点为主体,边是作为点的信息存在的,这一点很符合我们的思考规律。其次因为边采用vector保存,所以不用担心重边丢失的问题。邻接表逊色于邻接矩阵的地方恐怕就只有查询两个点之间是否有边了,在邻接表里面你必须遍历整个当前点上的to才能判断是不是能和另外一个点相连。但相对的,如果图中的点连接的边不多的话(这时候的图可以称为“疏松图”,反之,“稠密图”),邻接矩阵下的O(n)的遍历在邻接表下就快多了。

链式前向星(静态建表的邻接表实现)

上文中我们还提到了“如果我们给每一条边挂载一个数对,上面记载了边的两端所连接的节点的序号,会怎么样?”,其实链式前向星就是这种思路。

在这里假定你已经很明白链表的工作方式了,链式前向星其实就是图上所有边按照某种特殊的方式组成的链表。因为比较难理解,我先上代码。

使用上,还是先编号,然后挨个边处理,直接调用addEdge()方法就可以,查询一个节点所连出的边是,使用上面代码里iteration()里的方法,利用一个略微奇怪的for循环就可以办到。

我们不妨直接从代码的实现来分析链式前向星的工作原理,结构体里面的head是每一个节点在容器(数组)中所对应的第一条边的位置,next是每一条边在容器中所对应的同一起点的下一条边的位置,to则是真正的存储某一条边是指向哪一点的。

再看加边操作,注意到方法里的q是静态变量,这一点非常重要,q的作用是指示当前存储边的容器的末端(注意“末端”指的是并不是最后一个元素,而是其后的空地)的位置,相当于STL迭代器的end(),每一次加边的时候,要在to的末端写入新加边的信息,然后通过head[_from]提取出起点最近加的一条边的位置,然后我们要把新加的边的next指向那一条边,最后修改head,使得最近添加的边变更为新边,同时末端向后移动以供下一次添加之用。

理解了这样的加边方法,查询一个点连出的边的方法也就很好理解,要查询一个点的连出边,我们要先查head,知道这个点最近添加的那条边在哪里(查询结果在这里是j),然后比这条边早一些添加的就是next[j],再早一点的就是next[next[j]],更早一点的是next[next[next[j]]],再早一点的是……,就这样我们一直往时间添加时间更早的边查,直到查到空节点(用来标记链表结束)。

可以发现,链式前向星相对于邻接表的vector实现,常数更小。同时如果想直接遍历每一条边,而不考虑顺序,可以直接遍历to数组(当然,为了知道每条边的起点,你可能还需要建一个from数组),这就使得我们可以从边入手解决问题。因为是邻接表,我们也可以以点为中心来考虑问题。基本可以说链式前向星在各方面都优于邻接表的vector实现。

如果你不用数组,而是用指针来实现,那就是“前向星”了。

暴力搜索

在讲搜索之前,我们还要再来一点关于图的话题,那就是“树”,当然不是种出来的树,而是一种特别一点的图,不过就像你在大街上看到的各种树一样,能被称为一棵“树”的图一定要满足以下几种特征:

  • 每两个点之间有且仅有一条路径
  • 没有环,而且只要再添加一条边,就一定会出现环
  • 只要去掉一条边,就无法保证第一条性质
  • 只要增加一个点,为了保证第一条性质就必须还要增加一条边
An Example of Tree
An Example of Tree

如果只有光秃秃的一个节点,其实也可以称为树,树上的边的方向性也没有要求,可以有向也可以无向,当有多棵“树”同时存在的时候,这些互相没有相交的树共同组成的图也被称作“森林”。

g04
An Example of Forest

自然界的树都是有根的,同样的,有时候为了分析问题的便利,我们也会选取树上的某个节点作为“根节点”。选取了根节点的树这时候也称为“有根树”。

选取了根之后,伴随之而来的还有节点与节点之间的“辈分关系”,我们把根视为辈分最大的祖先,他连接的所有点都是它的“孩子”,而对于他连接着的所有点来说他就是这些点的“父亲”。这样的关系对于所有的节点都是一样的,我们注意到了,在一棵树上,每个节点可以有好多孩子,但是只能有一个父亲,而对于没有孩子的节点,我们对他还有一个称呼叫“叶子节点”,对于有同一个父亲的若干个节点,他们互称“兄弟节点”。

Relation on a Tree
Relation on a Tree

细心的你也发现了,上面这幅图从上面到下面颜色是越来越深的,没错,我想借此来表达有根树的“深度”概念。对于根部,他的“辈分”最大,但是他的“深度”是最小的,父亲的深度始终是比孩子节点的深度大1的。

理解了上面的这些概念,我们就可以开始说“暴力搜索”了。

我们说的“搜索”是什么

我们对搜索的认识,恐怕都是来源于“百度”、“谷歌”,也就是“从所有的信息中找出我们需要的信息的这一过程”,而我们现在接下来要说的“搜索”虽然感觉上还是和你键入几个关键字然后敲回车有一定区别的,但是实质上其实是一样的,不过现在这个过程要交给你亲自去实现。

试想这么几个问题,给你一个表示各个景点之间连通关系的图,现在让你找13号点在哪里,你如何“系统地”完成这个寻找过程?给你一个迷宫,里面有好多墙壁,现在要你找出脱出迷宫的最短路线,你又该如何“系统地”完成这一过程?更直接地,给你一棵树,制定一个根部,你能“系统地”把这棵树的亲子关系和深度都算出来吗?

这些问题,对于你来说可能就是瞟一眼那样简单,不过你知道计算机可是没有眼睛的,也没法扫视全局,因此“系统性”的算法就显得非常重要,也就是说你要有一种“套路”,而不是随便去瞟一眼这么简单。

接下来我们要介绍两种最为常见的搜索“套路”,深度优先搜索和广度优先搜索。在学习这些之前,我已经假定你理解了我上面所讲的的概念,以及递归(调用栈)队列的知识。

深度优先搜索(Depth First Search)

理解深度优先搜索(DFS)的最佳途径就是从“树的先序遍历(DLR)”开始,所谓“遍历”就是把树的每一个节点都走一遍。树的先序遍历,是指对于给定的一棵有根树,从这棵树的根部开始,不断尝试进入儿子节点(下潜),直到进入了叶子节点,然后才会返回到上一层,继续查找下一个儿子节点进入,通过不断重复这一过程,直到所有的节点都被进入并最终返回根部。简单的说就是:不断尝试探底,不走重复的路。下面举个例子来解说:

在这里我给出了一棵树,并且设定好了根部,同时因为我们的起点在根部,我把根部标记为1.

g06
Example Tree to Show DLR

根节点(1号节点),连接了两个儿子节点,按照上文所述的思想,我们优先访问最左面的那个,我们把它标记为2,并进入这个节点。

g07

 

进入2号节点之后,我们顺着刚才的思路,不断下潜,最后我们到达了叶子节点4号。

g08

 

现在我们发现没有可以用的孩子节点了,那么我们就要回到当前节点的父亲那里去,也就是3号节点。在3号节点,我们发现了除了已访问的4号节点之外的另外一个儿子,我们把它标记为5号节点,并进入。

g10

我们在5号节点又遇到了4号一样的情况,没有儿子,那样的话我们就要返回父亲节点3号。当我们返回3号,我们发现儿子已经走了个遍了,这个时候我们又要返回父亲节点2号,在2号同样没有可以没走过的儿子了,我们返回到2号的父亲节点1号。

g11

等我们回到了一号节点,我们又可以找到新的没有走过的儿子了,于是我们按照刚才的调子,进入这个儿子,这个节点已经是我们走过的第6个新节点了,给他标号6,然后我们又找到了他的儿子,进入,标号7。

g12

7号节点又是叶子节点,于是我们返回到他的父亲6号,然后发现还有一个没走过的儿子,于是进入,标号8。

g13

8是叶子节点,返回6,6没有没走过的儿子,返回1,1没有没走过的儿子。好了,任务完成了!

g14

以上就是“树的先序遍历”,是不是很简单?而DFS其实就可以理解成先序遍历在各种其他情境的推广,比如各种“图的遍历”、迷宫搜索(可以转化为图)、找出联通块(水洼问题)等等。通过思考我们也发现了,DFS实现起来的最佳方式就是递归,递归可以完美的还原我们的“下潜(发动递归)”和“返回(函数返回)”动作。下面我给出使用DFS遍历图的实现,使用了vector邻接表,所有访问到的节点,均会在标记数组vis中被标true。

如果你还是一头雾水,不妨试着将上面我做演示的那棵树建立成图,然后手动模拟一边这份实现的执行过程,就能理解了(前提是你必须知道递归的原理)。

一旦你发动了dfs(a),那么在搜索执行完毕之后,所有与a号节点直接或间接连通的点都会被在vis中标记,所以只要对这份实现稍加改动,我们就可以解决“水洼问题”了。而要想解决“迷宫出路”这种问题,我们还要稍微动下脑筋,思考一下vis这个标记数组应该怎样活用,怎样利用vis让dfs达到我们想要的效果(在这份实现中,一旦一条路被走过,就无法再次走过,而在迷宫中,我们很有可能要走之前走过的道路,这样我们就要适时地复原vis标记)。

广度优先搜索(Breadth First Search)

相对于DFS,广度优先搜索(BFS)也许更加直观一点,我们还是从“树的遍历”说起。对于一棵给定的有根树,我们依然从根开始入手,不过这次我们建立了一个队列,队列存储的是“状态”,最开始队列是空的,要开始搜索,我们要给他加入“当前在根节点”这一状态,之后我们不断拉取队伍的队首,然后分别把我们进入了各个儿子的状态逐一加入队列,直到队列清空,这个时候我们一定把每一个“在XX节点”的状态都经历过了,所以我们是走遍了整棵树。

我在这里依然用在DFS里的那棵树来举例子,图下面的方括号,表示队列的变化,左半方括号表示队列头,右半方括号表示队列尾。

最开始,我们的队列里只有1号状态,我们给它拿出来,然后发现他有两个儿子,于是分别创建进入2号儿子的2号状态和进入3号儿子的3号状态,并将他们加入队列尾端。

g15
[1] -> [2,3]
接下来,我们取出队列头的2号状态,我们发现它只有一个儿子,我给他标号4,于是把“进入4号节点”的4号状态加入队列。

[2,3] -> [3,4]
[2,3] -> [3,4]
接下来,取出队列头的3号状态,我们发现它有两个儿子,在这里标号为5和6,于是借此生成5号和6号状态,加入队列。

[3,4] -> [4,5,6]
[3,4] -> [4,5,6]
之后,取出队列头的四号状态,发现在这个状态所在的4号节点有两个儿子,在这里标号7和8,同时据此创建状态并加入队列。

[][]
[4,5,6] -> [5,6,7,8]
最终,队列弹出的5,6,7,8号状态均是在叶子节点的状态,无法创建新状态,队列就此清空,我们完成了遍历任务!来看一下我们整个BFS的全貌吧:

State tree of the whole BFS process
State tree of the whole BFS process

相信你已经可以基本理解BFS的工作方式了。

显然光会个遍历树是不够的,将上面所讲述的思考方式拓展一下,BFS也可以完成“图的遍历”,“迷宫最短路”等问题,下面我会给出一种用于遍历图的BFS实现,图的存储方式采用vector实现的邻接表。

 

选择适合的搜索方式

一招鲜显然并不能吃遍天,DFS,BFS中的任何一个都不能应付全部的场合。DFS使用递归实现,因此当搜索深度比较大的时候就存在巨大的栈溢出风险,而实用模拟栈实现的DFS又十分复杂,得不偿失,因此当栈空间不足以支持DFS时,必须换用BFS。BFS相对于DFS,实现相对比较繁琐,如果使用STL queue的话,会带来一些常数上的劣势(这种劣势在SPOJ等黑心OJ上十分明显),模拟队列又可能会占用大量内存。因此我们需要根据问题的实际来考虑使用哪种搜索方式。

一般来说,DFS在求连通性问题上具有十分的优势(Tarjan SCC/DCC算法均基于DFS),而BFS在求最短路问题上占上风(Dijkstra/SPFA算法均基于BFS),掌握好这两种算法是学好图论的基础。如果你够细心的话,你会发现我们在DFS的同时给树进行了编号,那个编号其实叫做“DFI(DFS序)”,这个东西有着一些神奇的应用。同时DFS和BFS又可以升级为一种考虑问题的思想,当然这些高级一些的问题就需要我们在练习的时候慢慢体会了。

 

本文系hahaschool原创,同时作为Tic ACM Club讲稿,未经许可禁转载。

 

生成树小总结

无向图最小生成树

Prim算法

这个实现做的非常不好,需要改进。对付稠密图,Prim更胜Kruskal一筹。

Kruskal算法

[这个实现等待填坑]

Borůvka算法

[这个实现等待填坑]

有向图最小生成树(最小树形图)

复杂度O(V * E),以下代码仅存储边,而且会对存储结构发生破坏,请注意。实现来源于国立台湾师范大学。我对这份代码进行了更加详细的注释。

适用于固定了生成树的根的情形

适用于生成树的根无法确定的情形

引用自GentieH,谢谢。

建立虚拟节点x,令x连所有的点,权值为所有边权的总和+1,求得最后结果减去该值即可,由于虚拟节点的存在,不会显式地出现孤立点,这时通过判断如果存在多与1个节点的pre为root,则说明无解。如果需要求出根节点,由于之前将x与图中的点连边时,我们按顺序连的话,考虑到可以用边去标识点,对于每一个终点v,如果它的pre为root,则标记这条边who,在求结果时,让who-E即可。

要求输出方案的情形

CF240E

 

次小生成树

[Pending Session]

增量最小生成树

[Pending Session]

最小瓶颈生成树

[Pending Session]

生成树问题混杂其他类型问题

二分图小总结

知识

二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配

这一篇已经足够了。

模板

匈牙利算法,复杂度O(V*E),使用“vector邻接表”存储图。MAXN为单边最大节点数量,需要按照题目要求调整,INF是理论最大值不够的话按照题目要求调整。左手边和右手边的节点序号从0开始,建图前,执行init,并正确配置nx(左手边节点数量)和ny(右手边节点数量),BGM_H()返回最大匹配数。

Hopcroft-Karp算法,复杂度O(sqrt(V) * E),适配方法同匈牙利算法模板,调用是BGM_HK(),不适合活用。

配套练习

二分图・ア

POJ 1274 The Perfect Stall(教学题)
POJ 2446 Chessboard(骨牌模型转化)
POJ 2594 Treasure Exploration(允许相交的最小路径覆盖)
POJ 1325 Machine Schedule(适当建图,最小点覆盖问题)
POJ 1469 COURSES(教学题)
HDU 3225 Flowers Placement(匈牙利算法在DFS中的剪枝作用)

 

关于欧拉回路和欧拉路径

请留意本文转载自http://www.cppblog.com/abilitytao/archive/2010/07/26/121319.html

如果侵犯了您(原作者)的权益请联系我删除,谢谢。

定义:
欧拉回路:每条边恰好只走一次,并能回到出发点的路径
欧拉路径:经过每一条边一次,但是不要求回到起始点

①首先看欧拉回路存在性的判定:

一、无向图
每个顶点的度数都是偶数,则存在欧拉回路。

二、有向图(所有边都是单向的)
每个节顶点的入度都等于出度,则存在欧拉回路。

三.混合图欧拉回路
混合图欧拉回路用的是网络流。
把该图的无向边随便定向,计算每个点的入度和出度。如果有某个点出入度之差为奇数,那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度,也就是总度数为偶数,存在奇数度点必不能有欧拉回路。
好了,现在每个点入度和出度之差均为偶数。那么将这个偶数除以2,得x。也就是说,对于每一个点,只要将x条边改变方向(入>出就是变入,出>入就是变出),就能保证出 = 入。如果每个点都是出 = 入,那么很明显,该图就存在欧拉回路。
现在的问题就变成了:我该改变哪些边,可以让每个点出 = 入?构造网络流模型。首先,有向边是不能改变方向的,要之无用,删。一开始不是把无向边定向了吗?定的是什么向,就把网络构建成什么样,边长容量上限1。另新建s和t。对于入 > 出的点u,连接边(u, t)、容量为x,对于出 > 入的点v,连接边(s, v),容量为x(注意对不同的点x不同)。之后,察看是否有满流的分配。有就是能有欧拉回路,没有就是没有。欧拉回路是哪个?查看流值分配,将所有流量非 0(上限是1,流值不是0就是1)的边反向,就能得到每点入度 = 出度的欧拉图。
由于是满流,所以每个入 > 出的点,都有x条边进来,将这些进来的边反向,OK,入 = 出了。对于出 > 入的点亦然。那么,没和s、t连接的点怎么办?和s连接的条件是出 > 入,和t连接的条件是入 > 出,那么这个既没和s也没和t连接的点,自然早在开始就已经满足入 = 出了。那么在网络流过程中,这些点属于“中间点”。我们知道中间点流量不允许有累积的,这样,进去多少就出来多少,反向之后,自然仍保持平衡。
所以,就这样,混合图欧拉回路问题,解了。
②.欧拉路径存在性的判定

一。无向图
一个无向图存在欧拉路径,当且仅当   该图所有顶点的度数为偶数   或者  除了两个度数为奇数外其余的全是偶数

二。有向图
一个有向图存在欧拉路径,当且仅当 该图所有顶点的度数为零     或者 一个顶点的度数为1,另一个度数为-1,其他顶点的度数为0

三。混合图欧拉路径
其实整篇文章只有这部分是我写的哈,灰常不好意思,只是网上的同志们写的太好了,实在没有必要重复劳动,不知道大家有没有发现,求欧拉路径的第一步一定是求欧拉回路,在混合图上也不例外,如何判断混合图欧拉回路问题的存在性呢?首先,我们用上文所说的方法判断该图是否存在欧拉回路,如果存在,欧拉路径一定存在。如果欧拉回路不存在,那么我们枚举欧拉路径的起点和终点,连接一条无向边,然后再用最大流判断是否存在欧拉回路即可。

Scroll to top