AcWing《算法基础课》第3章 搜索与图论
深度优先遍历DFS
模板：
bool st[N]; // 标记是否用过
int h[N], ne[N];
int dfs(int u)
{
if (...) {...; return;} // 输出结果，记得加return语句（或者后边部分用else括起）
st[u] = true; // st[u] 表示点u已经被遍历过
for (int p = h[u]; p != -1; p = ne[p])
{
int v = e[p];
if (!st[v]) dfs(v);
}
st[u] = false; // 恢复现场
}
说明：
- 空间复杂度为$O(h)$，对空间复杂度高的考虑DFS
- 不具备最短性
宽度优先搜索BFS
模板：
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int u = q.front();
q.pop();
for (int p = h[u]; p != -1; p = ne[p])
{
int v = e[p];
if (!st[v])
{
st[v] = true; // 表示点j已经被遍历过
q.push(v);
}
}
}
说明：
- 如果手动实现
queue，则容量一般取N * N - BFS只适用边权为
1的迷宫
拓扑排序
模板：
int d[N]; // 入度
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
说明：
- 有向无环图又称拓扑图
- 有向无环图一定至少存在一个入度为0的点（反证法 + 抽屉原理证明）
- 当循环结束后，若队列的长度为
n，则拓扑排序存在 - 在添加边时，可以顺便统计入度
- 可以使用其它数据结构存储结果（例如线性表，栈等，甚至是集合）
- 时间复杂度是$O(n+m)$
dijkstra算法
朴素dijkstra算法
模板：
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist); // 0x3f3f3f3f作为距离的“最大值”
dist[1] = 0; // 自己到自己的距离为0
for (int i = 0; i < n - 1; i ++ ) // 执行n-1次（自己到自己的距离已经确定）
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1; // 不可达
return dist[n];
}
说明：
- 由于最多有$10^5$条边，且每条边的长度不超过$10^4$，因此最大距离不超过$10^9$，
0x3F3F3F3F比$10^9$大一些，因此可当做距离的最大值。好处是只用一行memset(d, 0x3f, sizeof d)就能实现把d数组各值初始化为“最大值” t == -1 || dist[t] > dist[j]使得t不必选第1个标记，实际上t = 1也是可以的，只需把循环条件从j = 2开始就可以min(dist[j], dist[t] + g[t][j])不要错写成min(dist[j], g[1][t] + g[t][j])- 对于重边的条件，不能使用编译器赋予的初值
0，而应该赋予一个比边长最大值更大的值，例如memset(g, 0x3f, sizeof g)，然后用g[a][b] = min(g[a][b], c)记录最小的重边即可 - 时间复杂度为$O(n^2+m)$
堆优化dijkstra算法
模板：
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x7f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
heap.push({0, 1}); // first存储距离（顶点1到顶点second的距离），second存储尾顶点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x7f7f7f7f) return -1;
return dist[n];
}
说明：
- 边长最大值为$10^4$，最多有$1.5\times10^5$条边，因此距离最大值为$1.5\times10^9$，因此
0x3f3f3f3f不可代表最大值，可用0x7f7f7f7f代替 - 改用邻接表数据结构
- 使用小根堆优化查找最小距离的过程
- 小根堆可能存在冗余数据
- 算法类似BFS，因为在修改其它顶点最短距离的过程中，堆优化版本并没有遍历所有的顶点，而是遍历所有与当前选取的最小顶点有关的边
- 时间复杂度为$O(m\text{log}n)$
Bellman-Ford
朴素Bellman-Ford算法
模板：
int n, m, k; // n表示点数，m表示边数，k是路径的最大边数
int dist[N], backup[N]; // dist[x]存储1到x的最短路距离
// 三元组
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x7f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式（存在更新），就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < k; i ++ ) // 如果没有k，则用n代替k
{
memcpy(backup, dist, sizeof dist); // 备份，防止读后写
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], dist[a] + w)
}
}
if (dist[n] > 0x7f7f7f7f / 2) return -1;
return dist[n];
}
说明：
- 除了可以用邻接矩阵和邻接表外，还可用三元组存储图
- 允许存在负权边，而Dijkstra算法不允许
- 外循环次数决定最小路径的最大边数
- 若第
n次迭代有修改，根据容斥原理知道，一定存在负权环（整个环的权重和为负数） - 实际应用：换乘不超过$k$次的最短路径（限制路径的边数）
- 若第
backup用于保存上次迭代的结果，避免“写后读”。Dijkstra算法不存在这种情况- 由于存在负权回路（注意不是负权边），因此负权回路有可能把自定义的无穷大
0x7f7f7f7f变小，由于最多修改$10000\times10000=10^8$，而0x7f7f7f7f$>2\times10^8$，故0x7f7f7f7f / 2依旧是“无穷大”，故可用dist[n] > 0x7f7f7f7f / 2判断是否是无穷大 - 时间复杂度为$O(mn)$
队列优化Bellman-Ford算法——SPFA算法
模板：
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x7f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false; // 已出队，因此队列不再包含顶点t，需要重置为false
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x7f7f7f7f) return -1; // 如果题目保证不存在负权回路（不是指负权边），则可这么写
return dist[n];
}
说明：
- 用队列优化更新最短距离的过程，核心思想是
dist[u]发生改变，dist[u] + w才有可能满足< dist[u]- 用队列保存最短距离发生改变的顶点（其它数据结构也可以，不一定是队列）
- 用
st记录在队列中的顶点，避免重复更新 - 由于每次只更新与出队顶点相关的边，因此不会出现“写后读”现象，故改进的bellman-ford算法不需要额外的数组保存上次迭代的结果
- SPFA算法有点像堆优化的Dijkstra算法，但后者依赖优先队列，而前者不需要
- 大多数情况下，Dijkstra算法能解决的问题，SPFA都比它更好，而且适用负权边，因此如果没有限制路径最大边数的情况下，优先考虑SPFA算法，如果过不了就考虑堆优化的Dijkstra算法
- 平均时间复杂度为$O(m)$，最坏时间复杂度为$O(mn)$
- 若要判断负环，则需要额外维护一个数组
cnt，用于记录各个最短路径的边数，当边数≥顶点数n时，则一定存在负环
Floyd算法
模板：
const int INF = 1E9;
// 初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
说明：
- 最短距离需要把d[i][i] = 0;
- 时间复杂度为$O(n^3)$
Prim算法
模板：
cosnt int INF = 0x3f3f3f3f;
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离(集合到点u的距离)
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF; // 非首次遍历时，出现集合到其它点都是无穷大的情况，则图为非连通图
if (i) res += dist[t]; // 第1次迭代得到的dist为无穷大，没意义
st[t] = true;
for (int j = 1; j <= n; j ++ )
if(!st[j]) dist[j] = min(dist[j], g[t][j]); // 可不加if，集合内点的dist应失去意义（受自环影响）
}
return res;
}
说明：
- 注意最小生成树解决的是无向图问题，因此存储边时要添加两条有向边
- 允许存在负权边、自环、重边
- 对于自环，需要先保存最短路径长度，再更新集合到其它点的距离，避免负权自环更新自己，出现写后读问题
- 对于重边，需要初始化各个点的距离为INF，然后用
min读入边
- 应用场景：多城市发电站的选址问题
- 可类似Dijkstra算法，用堆优化Prim算法，时间复杂度为$O(m\text{log}n)$，但由于这个算法只适用稀疏图（因为如果是稠密图的话，性能还不如朴素的Prim算法），对于稀疏图来说，$n$≈$m$，此时性能和kruskal算法接近$O(m\text{log}m)$，而kruskal算法代码更简洁，因此一般不用堆优化的Prim算法
- Prim算法和Dijkstra算法非常相似
- Prim算法更新其他点到集合的距离
- Dijkstra算法更新其它点到起点的距离
- 采用邻接矩阵保存图，适用稠密图，时间复杂度为$O(n^2+m)$
Kruskal算法
模板：
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
// 三元组
struct Edge // 存储边
{
int a, b, w;
// 重载<，用于sort排序
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m); // 快排，+m是地址运算，得到数组末尾
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0; // cnt统计边数
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF; // 边数小于n-1，不连通
return res;
}
说明：
- 用于求解稀疏图的最小生成树
- 采用三元组存储图时，没必要保存两条有向边
- 实际上是并查集的简单应用，可参考题目
- 由于是稀疏图，$n$≈$m$，因此没必要在遍历边时提前判断集合
a中是否有n个顶点 - 时间复杂度$O(m\text{log}m)$，主要来自排序步骤
- 由于需要对结构体数组排序，因此需要重载
<
染色法
用途：
判断二分图
模板：
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c; // 染色
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!color[j])
{
if (!dfs(j, 3 - c)) return false; // 用3-c实现交替染色
}
else if (color[j] == c) return false;
}
return true;
}
bool check()
{
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (!color[i])
if (!dfs(i, 1)) // 这里不需要3-c，因为这里进入的都是未染色的起点，换句话说是森林另一棵树的根
{
flag = false;
break;
}
return flag;
}
说明：
- 用邻接表存储图，注意无向图的边数为
2m - 核心思想：一个图是二分图，当且仅当图中不含奇数环（环的边数是奇数）
- 时间复杂度$O(n+m)$
匈牙利算法
用途：
二分图的最大匹配
模板：
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 标记已遍历
if (!match[j] || find(match[j])) // j未被匹配，或j已经匹配但其配对对象可选其它的匹配
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
说明：
- 用邻接表存储图，但不必存放双向边，只需存储单向边，因此最大边数为
M，而不必用2M - 核心思想：
- 假设a和b是左边顶点，c和d是右边顶点，a和b都能匹配c，但a还可以匹配d
- 当a匹配c后，b没有右边顶点可匹配
- a存在另一个可匹配顶点d，因此把a改成匹配d，这时b再匹配c
- 最坏时间复杂度$O(nm)$，但实际上会远远小于该复杂度
Bellman_ford算法中，dist[b] = min(dist[b], dist[a] + w)应该是dist[b] = min(dist[b], backup[a] + w)，使用上一次迭代的结果，同时，这个算法最后如果不成立返回-1是有点小毛病，如果算出来结果就是-1怎么办，不影响acwing上的数据，但是建议这里函数改为void，在主函数进行判断就可以避免这个问题
好滴，感谢指出问题！