算法

最短路径问题

导引图的存储

采用邻接矩阵：n个结点，采用一个nxn矩阵，矩阵第n行第m列存储了从n到m的边的权值

如果图是无向图，则对应邻接矩阵为对称矩阵

导引问题畅通工程

某省修建了很多路，从一个城镇到另一个城镇有许多方案可以选择，已知起点和终点，请计算最短的路径

基本思想

按照最短路径的长度递增的次序，依次求得源点到各点的最短路径

路径长度最短的最短路径特点：一定是直达的（反证法可证明）

步骤

首先找出最短的（$v_0,v_2$）
找出第二短的最短路径（要么直达，要么经过v₂到达，反证法也可证明）
松弛操作：检查v₀通过v₂到达的点能否比直达更近，若更近就更新
找出第三短的最短路径，继续进行松弛
对每个结点每次只比较原来的最短距离和通过新结点到达的最短距离

迪杰斯特拉算法

状态转移方程：$Dist[k]=min(Map[i][k]+Dist[i],Dist[k])$，u为刚刚求得的最短路径结点

复杂度分析

最坏情况下，求两点之间最短路径为求所有点之间最短路径（所求两点是最长的最短路径），复杂度O(n²)

代码实现

输入：第一行两个正整数N和M，分别代表城镇数目和已修建的道路数目，接下来M行每行三个整数，为A，B，X，代表A到B的双向道路长为X，再下来一行有两个整数S和T，表示起点和终点

解释：

Map[a][b]=min(Map[a][b],dis); \\防止有起点和终点相同但长度不同的边，只保留最短的
Dist[i]=min(Dist[i],Map[start][i]+Dist[start]) \\在新增结点可达结点i的情况下比较是否能更新
if(visit[i]&&Dist[i]<Min){next=i;Min=Dist[i];} \\如果可达且未计算过该结点，将该结点作为下一个该被计算的结点，同时更新最短路径长度，循环结束后Min就是最短路径长度，next就是最近结点
if(Min = = inf) break; \\没有路径
start=next;visit[start]=0; \\将start更新为next，同时标记为已处理

思考

如果起点和终点不止一个，如何求解

解法：新增一个起点，到每个起点的距离为0，新增一个终点，到每个终点的距离为0

如果要求输出路径，如何求解**

解法：采用一个数组存储，记录该点最短路径的上一个点是谁

广度优先搜索 BFS

队列

特点

先进先出
从队头出队
从队尾入队

STL中队列的用法

创建：queue<元素类型> 队列名；
队尾添加元素：队列名.push(元素名)；
去掉队首元素：.pop();
访问队首：.front();
访问队尾：.back();
判断是否为空：.empty();
返回队列大小：.size();

例题1 二叉树的层次遍历

解法：

维护一个队列，将根结点入队，首先访问根结点
当访问到一个结点时，先访问该结点，然后将其左右孩子入队（孩子结点不为空结点）
只要队列不为空，就不断取队尾元素重复2

图的BFS

问题：可能存在重复访问

解法：采用一个数组，长度为结点数，记录每个结点是否被访问

例题2

解法：类似于二叉树的层次遍历，用数组记录该层楼之前是否来过

代码实现：

a数组保存K[i],vis数组保存是否访问，pos结构体level表示当前楼层，steps表示当前步数

例题3 分享可乐

两个杯子容量分别是N和M，可乐的体积为S，三个之间可以互相倒可乐，但是杯子和可乐瓶都没有刻度，且S==N+M，若能平分可乐，则输出倒可乐的最少次数，若不能输出-1

解法：以每个杯子的可乐多少作为状态，同时附带当前操作次数，类似例题2，采用三维数组做标记

例题4

给定位置a和b，计算象棋盘上马从a走到b的最少次数

解法：用两个数组存储马可走的坐标变换，状态为当前坐标和当前步数

BFS基本思想

从初始状态S开始，利用规则，生成所有可能的状态，构成下一层结点
检查是否出现目标状态G，若未出现，就对分别该层所有结点依据规则生成下一层的结点
对新一层的结点继续检查是否出现G，若未出现，继续重复2，直到出现为止

深度优先搜索 BFS

导引二叉树的先序中序后序遍历

解法：递归

思考：

给定先序和中序遍历结果，能否确定二叉树? 可以

每次确定根和左右子树，递归

给定中序和后序? 可以

每次确定根和左右子树，递归

给定先序和后序？不行，无法确定根结点

深度优先搜索 DFS

导引问题斐波那契数列

步骤：

先写出口
再写普通情况

例题1

输入一个正整数n，按照字典序输出1到n的全排列，每个排列输出一行

解法：思考第一位，若第一位确定，剩下为n-1位的全排列

$f(n)=n*f(n-1)$

代码实现

step 代表准备处理第几个数字

思考：若任意n个数怎么解决

解法：将输入的n个数保存在数组a中，只需将输出的语句改为printf("%d",a[num[i]]);

例题2 迷宫问题

有一个古老的迷宫，有一只小狗在迷宫之内，迷宫的布局是n行m列，恰好在第t秒门开，S表示起点，D表示出口，每秒行动一个格子且不能停留或重复走，X表示墙，.表示路

解法：DFS，考虑若采用BFS，无法剪枝（不同时间到达同一地点也需要考虑），效率极低

DFS剪枝：

如果可走的总数小于时间，则一定不能逃离
奇偶性剪枝：把地图看成01相间的矩阵，定义行号加列号为奇的就是奇点，偶点同理，则0只能走到0，1只能走到1，奇偶性一致需要偶数秒，相反需要奇数秒

代码实现

统计墙的数量方便剪枝，等于t也不行因为开始位置也占了一格

if(temp<0||temp%2==1) return \\若当前剩余时间小于最少所需步数或者剩余时间和所需步数奇偶性不同，则剪枝

if(escape) return; \\若成功逃出，结束递归，若不写会一直递归

Map[si+dir[i][0]][sj+dir[i][1]]='.'; \\回溯，将之前走过的路恢复原状

思考：若改成t秒以后会关门，该如何做？

解法：采用BFS，求出走到门的最短时间

二分匹配算法

定义：一个图的所有顶点可以被分成两个集合，所有边的两个顶点分别属于两个集合

即任意两个同集合的顶点之间都没有边

二分图的最大匹配

匈牙利算法

基本思想：

设两个集合分别为男生和女生，从男生中任选一个，将其与一个有边的未匹配过的女生匹配，然后下一个
若有两个男生同时匹配同一个女生，则检查之前已经匹配的那个男生有没有其他的匹配对象，若有，则将其与另一个女生匹配，将现在的男生与之前的匹配对象匹配，从而使匹配个数+1
- 例如，男1可以和女1和女2匹配，男2和女1匹配，则匹配到男2时将男1改成和女2匹配，男2与女1匹配
实现：即对每个男生都用一次DFS，若找到的女生已匹配，则递归调用，搜索已匹配女生对应的男生能否找到新的匹配对象

二分图的最小顶点覆盖

求二分图的最少顶点，使得每条边都至少和其中一个点关联，即用最少的点覆盖所有的边

例题严禁早恋

删除最少的顶点使得所有的边断掉

最少顶点数=最大匹配数

原理：删除一个点，则该点的所有边都不能再用

例题2 任务安排

解法：

建图：机器A的所有模式为集合A，机器B的所有模式为集合B，一个任务代表一个边
最少重启数即为用最少的模式覆盖掉所有的边，即最少顶点覆盖数
注意：若任务在开始模式就可以执行则不需要重启，预处理时去掉模式为a0或b0的任务

DAG图的最小路径覆盖

DAG图：有向无环图

用尽量少的不相交的简单路径覆盖所有的点，即用最少的边覆盖所有的点

例题4 空袭

解法：

将GAD图改成二分图，每个顶点分成两个，左边为起点集合，右边为终点集合
假设每个点放一个伞兵，则每匹配一次，就减少一个伞兵，得到最少路径覆盖数=顶点数-最大匹配数

最大独立集：任意两个顶点不连通构成的最大集合

同理可证明，最大独立集顶点个数=顶点数-最大匹配数

代码实现（任务安排）

if(u!=0&&v!=0) \\预处理，结点为0的边不统计

bool use[MAXN] \\use数组仅代表在一个左结点的DFS中是否访问过右结点

if(linker[v]==-1||dfs(linker[v])) \\若右结点未匹配或者其匹配对象可以匹配新的结点，则匹配

if(dfs(u)) res++; \\如果可以直接匹配或者能找到新的匹配对象则最大匹配数+1

注意use数组和linker数组的初始化：linker在所有DFS之前，每次DFS都需要；use在每次DFS之前，防止单次DFS重复搜索

组合博弈入门

组合游戏

有两个玩家
游戏的操作状态是一个有限的集合
游戏双方轮流操作
双方的每次操作符合游戏规定
当一方不能将游戏继续进行的时候游戏结束，获胜方为对方
无论如何操作，游戏总能在有限次操作后结束

必败点P：下一个选手一定失败的点

必胜点N：下一个选手一定胜利的点

必败点和必胜点的性质

所有的终结点都是必败点
从任何必胜点操作，至少有一种方法可以进入必败点
无论如何操作，必败点只能进入必胜点

取子游戏算法实现：

将所有终结位置标记为必败点
将所有一步操作能进入必败点的位置标记为必胜点
如果某个点开始的所有一步操作都只能进入必胜点，则该点标记为必败点
若在3找不到新的必败点，则算法终止，否则返回步骤2

例题玩游戏的小男孩

两个玩家，初始硬币在右上角，n x m 格子，每次可左、下、左下，到无法再移动就输了

解法：显然左下角是终结位置，则最后一行以此为PNPNPN…，倒数第二行为NNNNN…，倒数第三行为PNPNPN…，以此类推

规律：设坐标为( n , m ), 则 n 和 m 都是奇数为必败点，其余为必胜点

思考：可以看成两个牌堆，分别有 n 和 m 张牌，每次取一张或零张

例题 Nim游戏

两个玩家，三堆扑克牌，轮流操作，每次选择某一堆取走任意张，取完的人胜利

解法：显然终结位置为（0，0，0），定义 Nim-Sum 为两个二进制按位异或

定理一：对于nim游戏的某个位置 (x，y，z) , 当且仅当三个数的 Nim—Sum 等于0位于必败点

证明：首先对于不等于 0 的位置，可以通过一步操作使得异或结果变成0，显然，对于异或结果为 0 的位置，只能走到非 0 的位置

思考：对于某个必胜点，有几种可行的方案

解：异或结果最高位的 1 对应的位置有几个最高位是 1

SG函数 ( 图游戏 )

定义：$sg(x)=min{n\geq0:n<>sg(y)\quad for\quad y\in F(x)}$

即 x 结点的 sg 值是去除 x 的后继结点的 sg 值后的最小的非负整数

结论：sg 值为 0 的是必败点，非 0 是必胜点

证明：首先终结状态没有后继结点，所以终结状态的 sg 值是 0 ，从而所有以终结状态为后继结点的结点都是必胜点，此时 sg 值不可能为 0 ，显然 sg 值为 0 的结点后继结点只能为非 0 的结点

组合游戏的并

2人游戏，三个牌堆5，7，9，每人每次选择任意一堆取 1 - 3 张，取完的胜利

解法：

可看作三个牌堆小游戏的并

定理二：若干个小游戏的并的 sg 值为所有小游戏 sg 值的按位异或 ( 证明类似 sg 函数的证明 )

代码实现：

int k,a[100],f[10001];		//k 为规则数，a保存规则数组，f为 sg 函数
int sg(int p)
{
    int i,t;
    bool g[101]={0};	//标记数组，用来表示该数是否有后继结点的 sg 值占用
    for(i=0;i<k;i++)	//依次计算每条规则,
    {
        t=p-a[i];		//t对应的 sg 值等价于 t 减去规则确定的摸牌数的 sg 值
        if(t<0)  break;  //规则数组按升序，若无序就把 break 改成 continue
        if(f[t]==-1)  f[t]=sg(t);	//没求过,递归处理求后继的 sg 值
        g[f[t]]=-1;		//标记已用
    }
    for(i=0;;i++)		//从小到大枚举非负整数
    {
        if(g[i]==0) return i;	//没用过则返回i
    }
}