3. 搜索与图论（I）
3.1 DFS（深度优先搜索）
题目：给你一个数 \(n\)，按字典序将长度为 \(n\) 的全排列全部输出。\(1\le n\le 9\)。
思路：
运用 DFS 暴力搜索即可，时间复杂度 \(O(n!)\)。
如图 \(\texttt{3-1}\) 展示了 \(n=3\) 时的搜索过程：
初始时，\(3\) 个空都没有被填上。
第 \(1\) 个空填上 \(1\)：
第 \(2\) 个空填上 \(2\)：第 \(3\) 个空填上 \(3\)。 此时已递归 \(n\) 层，输出 \(1\;2\;3\)。
第 \(2\) 个空填上 \(3\)：第 \(3\) 个空填上 \(2\)。 此时已递归 \(n\) 层，输出 \(1\;3\;2\)。
第 \(1\) 个空填上 \(2\)：
第 \(2\) 个空填上 \(1\)：第 \(3\) 个空填上 \(3\)。 此时已递归 \(n\) 层，输出 \(2\;1\;3\)。
第 \(2\) 个空填上 \(3\)：第 \(3\) 个空填上 \(1\)。 此时已递归 \(n\) 层，输出 \(2\;3\;1\)。
第 \(1\) 个空填上 \(3\)：
第 \(2\) 个空填上 \(1\)：第 \(3\) 个空填上 \(2\)。 此时已递归 \(n\) 层，输出 \(3\;1\;2\)。
第 \(2\) 个空填上 \(2\)：第 \(3\) 个空填上 \(1\)。 此时已递归 \(n\) 层，输出 \(3\;2\;1\)。
具体实现可参考代码。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int path[15]; //存储路径
bool st[15]; //存储每个点是否被使用过
void dfs(int u) {
if (u == n) { //如果已经递归n层,说明已经构造出了一个全排列
for (int i = 0; i < n; ++i) printf("%d ", path[i]);
puts("");
return ;
}
for (int i = 1; i <= n; ++i) { //遍历1~n之间的所有数
if (!st[i]) { //如果i还没有被使用
path[u] = i, st[i] = 1; //将其加入路径中,并打上使用标记
dfs(u+1); //递归第u+1层
st[i] = 0; //恢复现场
}
}
}
int main() {
scanf("%d", &n);
dfs(0);
return 0;
}
题目：给你一个大小为 \(n\times n\) 的国际象棋棋盘，你需要在上面摆放 \(n\) 个皇后使它们不能相互攻击到，按任意顺序输出所有结果。\(1\le n\le 9\)。
思路：我们可以枚举每一行的状态，并分别用数组 \(col,dg,udg\) 来存储某一列/对角线/反对角线上是否有皇后。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int col[10], dg[20], udg[20]; //分别存储某一列/对角线/反对角线上是否有皇后
char ans[10][10]; //存储最终答案
void dfs(int u) {
if (u == n+1) { //递归终点
for (int i = 1; i <= n; ++i) { //输出方案
for (int j = 1; j <= n; ++j)
putchar(ans[i][j]);
puts("");
}
puts("");
}
for (int i = 1; i <= n; ++i) { //枚举每一列,此时推到第(u,i)格
if (!col[i] && !dg[u+i-1] && !udg[n-u+i]) {
col[i] = dg[u+i-1] = udg[n-u+i] = 1;
ans[u][i] = 'Q';
dfs(u+1);
col[i] = dg[u+i-1] = udg[n-u+i] = 0; //恢复现场
ans[u][i] = '.';
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
ans[i][j] = '.'; //初始化
}
dfs(1); //从第一行开始搜索
return 0;
}
3.2 BFS（广度优先搜索）
题目：给定一个 \(n\times m\) 的二维数组，其中 \(0\) 代表可以通行，\(1\) 代表不可通行。初始时有一人位于 \((1,1)\) 处，且他每次可以向上下左右各走一步，求出此人从 \((1,1)\) 走到 \((n,m)\) 的步数最小值。
数据保证有解。\(1\le n,m\le 100\)。
思路：
DFS 是每次沿着一个分支搜到底，而 BFS 则是每次扩展一层。可以用一个队列 \(q\) 来存储当前层的点，用 \(st\) 数组来标记一个点是否走过；对于 \(q\) 中的每个点的扩展点，若其没有被走过，则将其加入队列。同时用 \(d\) 数组记录每个点的步数最小值（显然每个点被第一次扩展到的步数即为其最小值）。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int N = 110;
int n, m;
int d[N][N];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; // 方向数组
bool map[N][N], st[N][N];
void bfs() {
queue<pii> q;
q.push({1, 1}); // 初始时队列里只有源点
while (q.size()) { // 当队列不空时,持续计算
auto t = q.front(); // 取出队头
q.pop(); // 将其弹出
int x = t.first, y = t.second; // 当前遍历到的点的横纵坐标
if (x == n && y == m) return ; // 如果当前点为(n,m)说明找到答案
for (int i = 0; i < 4; ++i) { // 遍历四个方向
int x_ = x+dx[i], y_ = y+dy[i];
if (x_ > 0 && x_ <= n && y_ > 0 && y_ <= m && !st[x_][y_] && !map[x_][y_]) // 判断是否越界或已经走过
q.push({x_, y_}), d[x_][y_] = d[x][y]+1, st[x_][y_] = 1;;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
scanf("%d", &map[i][j]);
}
bfs();
printf("%d\n", d[n][m]);
return 0;
}
题目：给定一个 \(3\times 3\) 大小的八数码游戏，其中包含 \(1\sim 8\) 的数字和一个表示空位的字符 x. 找出使完成游戏的最少步数，无解输出 \(-1\)。
思路：其实就是一个稍微复杂点的走迷宫，但是存储距离需要用到 unordered_map.
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
using namespace std;
string start, final = "12345678x"; // 为方便计算,将3*3方格压缩至1行
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int bfs() {
queue<string> q;
unordered_map<string, int> str; // 存储每个状态到初始状态的步数(即“距离”)
q.push(start), str[start] = 0;
while (q.size()) {
string s = q.front();
q.pop();
if (s == final) return str[s];
int pos = 0, x, y;
for (int i = 0; i < 9; ++i) {
if (s[i] == 'x')
pos = i;
}
x = pos / 3, y = pos % 3; // 计算行,列
for (int i = 0; i < 4; ++i) {
int x_ = x+dx[i], y_ = y+dy[i];
int pos_ = x_*3+y_;
if (x_ >= 0 && x_ < 3 && y_ >= 0 && y_ < 3) {
string s_ = s;
swap(s_[pos], s_[pos_]); // 交换相应位置
if (!str[s_]) str[s_] = str[s]+1, q.push(s_);
}
}
}
return -1;
}
int main() {
for (int i = 0; i < 9; ++i) {
char c; cin >> c;
start += c;
}
cout << bfs() << endl;
return 0;
}
3.3 树与图上的搜索
前置知识：
对于一张有向图 \(G\)，我们一般采用邻接表或邻接矩阵的方式存储。对于无向图，可以把无向边看作两条方向相反的有向边。
设有向图 \(G=(V,E)\)，其中 \(V\) 是点集，\(E\) 是边集，\((u,v)\) 表示从 \(u\) 到 \(v\) 的一条有向边，\(w(u,v)\) 表示 \((u,v)\) 这一条边的边权。设 \(n\) 为图上点的数目，\(m\) 为图上边的数目，即 \(n=|V|,m=|E|\)。 邻接矩阵 \(A\) 是一个 \(n\times n\) 大小的矩阵，通常的定义为：
\[A_{i,j}=\left\{\begin{array}{l} &0&i=j\\ &w(i,j)&(i,j)\in E\\ &+\infty&(i,j)\not\in E \end{array}\right.\tag{3.1} \]邻接表则包含了一个长度为 \(n\) 的表头数组 \(h\)，\(h_i\) 记录从 \(i\) 号点出发的第一条边的编号；长度为 \(m\) 的数组 \(e,ne,w\)，\(e_i\) 存储第 \(i\) 条边的终点，\(ne_i\) 存储从第 \(i\) 条边的起点出发的下一条边的编号，\(w_i\) 存储第 \(i\) 条边的边权。
邻接表的实现：
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) { // 加入一条长度为c的边(x,y)
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
//遍历u号点的所有出边
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
//...
}
3.3.1 树与图的深度优先搜索
题目：给你一棵包含 \(n\) 个节点的树，求出将这棵树的重心删除后剩余各个连通块的点数最大值。
重心：对于树中的一个节点 \(u\)，若将其删除后，剩余各个连通块的最大值最小，则称其为树的重心。
\(1\le n\le 10^5\)。
思路：本题中，我们假设 \(1\) 号节点为根节点。
从根节点出发 DFS 整棵树。函数 dfs(u) 返回以 \(u\) 为根节点的子树的大小 \(sum\)（包括其本身）。
令答案为 \(ans\)，则：
\[ans=\max(\text{dfs}(v_1),\text{dfs}(v_2),\cdots,n-sum_u),u\in[1,n],\{v_i,u\}\in E\tag{3.2} \]为避免重复计算，我们需要用一个 \(st\) 数组存储每个点是否已经被更新。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int ans = N;
int h[N], e[N*2], ne[N*2], idx;
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u) { //dfs(u)返回以u为根节点的树的大小
int res = 0, sum = 1; //res表示删去u后最大连通块大小
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) { // 遍历其子树
int t = dfs(j);
res = max(res, t);
sum += t;
}
}
res = max(res, n-sum);
ans = min(ans, res);
return sum;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) h[i] = -1;
int a, b;
for (int i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1);
printf("%d\n", ans);
return 0;
}
3.3.2 树与图的广度优先搜索
题目：给定一个 \(n\) 个点 \(m\) 条边有有向图，所有边长度均为 \(1\)，点的编号为 \(1\sim n\)。 求出 \(1\) 号点到 \(n\) 号点的最短距离。\(1\le n,m\le 10^5\)。
思路：从 \(1\) 号点出发 BFS，每次将可以被拓展到且没有拓展过的点加入队列。同时用一个 \(d\) 数组记录每个点到 \(1\) 号点的距离。第一次访问到 \(n\) 号点的时候即为 \(1\) 号点到 \(n\) 号点的最短路。（其实就是 Acwing 844. 走迷宫 换了个存图方式。）
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs() {
queue<int> q;
q.push(1); d[1] = 0;
while (q.size()) {
int t = q.front();
q.pop();
if (t == n) return ;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1)
q.push(j), d[j] = d[t]+1;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1, d[i] = -1;
while (m -- ) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
bfs();
printf("%d\n", d[n]);
return 0;
}
3.4 拓扑排序
拓扑序列：对于一个有向图中所有点构成的序列 \(A\)，使得图中的每条边 \((u,v)\)，\(u\) 在 \(A\) 中出现的次序在 \(v\) 前，则称 \(A\) 为该有向图的一条拓扑序列。
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环。请输出该图的任意一个拓扑序列，如果不存在则输出 \(-1\)。
思路：
我们可以记录每个点的入度 \(deg_i\) 并用手写队列维护一个入度为 \(0\) 的点的集合。 每次取出队头并遍历其所有出边，将其遍历到的点 \(i\) 的入度减 \(1\)，若此时 \(deg_i=0\) 则将其加入队列。最后判断队列中是否有 \(n\) 个元素即可。
拓扑排序可以判断一个有向图是否是有向无环图（DAG）。时间复杂度 \(O(n+m)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], ne[N], idx;
int top[N], hh, tt;
int deg[N]; //存储每个点的入度
void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}
void topsort() {
for (int i = 1; i <= n; ++i) { // 初始时将所有入度为0的点加入队列
if (!deg[i])
top[++ tt] = i;
}
while (hh < tt) {
int t = top[++ hh];
for (int i = h[t]; i != -1; i = ne[i]) { // 每次将当前度数为0的点加入队列
int j = e[i];
deg[j] --; // 相当于走过了一条边
if (!deg[j]) top[++ tt] = j;
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1;
while (m -- ) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
deg[v] ++;
}
topsort();
if (tt < n) puts("-1"); // 如果序列中没有n个点,说明拓扑序列不存在
else for (int i = 1; i <= n; ++i) printf("%d ", top[i]);
return 0;
}
3.5 最短路算法
我们约定：
- \(s\) 为最短路的源点；
- \(D(u)\) 表示从 \(s\) 到 \(u\) 的 实际 最短路长度；
- \(dis(u)\) 表示从 \(s\) 到 \(u\) 的 估计 最短路长度，且在任意时刻，都有 \(dis(u)\ge D(u)\)。 当最短路算法终止时，应有 \(dis(u)=D(u)\)。
3.5.1 Dijkstra 算法
3.5.1.1 朴素 Dijkstra
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 \(1\) 号点到 \(n\) 号点的最短距离，若无法到达则输出 \(-1\)。
\(1\le n\le 500,1\le m\le 10^5\)。
思路：
先介绍 Dijkstra 算法所用的松弛操作。
对于边 \((u,v)\)，松弛操作对应下面的式子：
\[dis(v)=\min(dis(v),dis(u)+w(u,v))\tag{3.3} \]即，我们尝试用 \(s\rightarrow u\rightarrow v\) （其中 \(s\rightarrow u\) 的路径取最短路）这条路径更新 \(v\) 的最短路长度；如果这条路径更优，则进行更新。
Dijkstra 的过程如下：将结点分为两个集合：已确定最短路长度的点集（记为 \(S\) 集合）和未确定最短路长度的点集（记为 \(T\) 集合）。开始时所有点都属于 \(T\) 集合。
初始化 \(dis(s)=0\)，其他点的 \(dis\) 均为 \(+\infty\)。
接着重复 \(n\) 轮迭代：
- 从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中；
- 对这个结点的所有出边进行松弛操作。
朴素的 Dijkstra 算法的时间复杂度是 \(O(n^2)\) 的。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510, MAXN = 2e9;
int n, m;
bool st[N];
int g[N][N];
int dist[N];
int dij() {
for (int i = 1; i <= n; ++i) dist[i] = MAXN;
dist[1] = 0;
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j) { // 每次找出当前离1号点的距离最短的点
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = 1;
// 松弛操作
for (int j = 1; j <= n; ++j) if (g[t][j] != MAXN) dist[j] = min(dist[j], dist[t]+g[t][j]);
}
return (dist[n] == MAXN) ? -1 : dist[n];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
g[i][j] = MAXN;
}
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
int ans = dij();
printf("%d\n", ans);
return 0;
}
3.5.1.2 堆优化 Dijkstra
模板：AcWing 850. Dijkstra求最短路 II
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 \(1\) 号点到 \(n\) 号点的最短距离，若无法到达则输出 \(-1\)。
\(1\le n, m\le 1.5\times 10^5\)。
思路：
注意到朴素 DIjkstra 中每次取出最短路最小的结点的代价是 \(O(n)\) 的，这个过程我们可以使用堆（优先队列）优化。
优先队列插入一个结点的代价是 \(O(\log m)\) 的，取出最小值的代价是 \(O(1)\) 的，故堆优化 Dijkstra 的时间复杂度为 \(O((n+m)\log m)=O(m\log m)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int N = 1.5e5+10, MAXN = 1e9+10;
int n, m;
bool st[N];
int dist[N];
int h[N], e[N], ne[N], w[N], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dij() {
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, 1});
dist[1] = 0;
while (q.size()) {
auto t = q.top(); // 取出堆头
q.pop();
int ver = t.second, dis = t.first;
if (st[ver]) continue;
st[ver] = 1;
for (int i = h[ver]; i != -1; i = ne[i]) { // 遍历其出边
int j = e[i];
if (!st[j] && dist[j] > dis+w[i]) { // 松弛操作
dist[j] = dis+w[i];
q.push({dist[j], j});
}
}
}
return (dist[n] == MAXN) ? -1 : dist[n];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1, dist[i] = MAXN;
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int ans = dij();
printf("%d\n", ans);
return 0;
}
3.5.2 Bellman-Ford 算法
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，边权可能为负数，图中可能存在负权回路。请你求出 \(1\) 号点最多经过 \(k\) 条边到达 \(n\) 号点的最短路，若无法到达输出 impossible.
\(1\le n,k\le 500,1\le m\le 10000\)。
思路：
先介绍普通的 Bellman-Ford 算法（即无边数限制）：初始化 \(dis(1)=0\)，其余点的 \(dis\) 为 \(+\infty\)，循环 \(n\) 次，每次遍历 \(m\) 条边并对其进行松弛操作，时间复杂度 \(O(nm)\)。 若加上 \(k\) 条边的限制，则改为循环 \(k\) 次即可。
代码实现时有一个细节需要注意，每一次循环时我们需要用一个 backup 数组来存储上一次的 \(dis(i)\)，否则会出现串联现象（即用已更新过的边去更新其他的边）。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e5+10, MAXN = 2e9;
int n, m, k;
int dist[N], backup[N];
struct Edge {
int a, b, c;
} e[M];
void bellman_ford() {
dist[1] = 0;
for (int i = 1; i <= k; ++i) { // 最多k条边,重复k轮迭代
for (int j = 1; j <= n; ++j) backup[j] = dist[j]; // 存储上一次的结果
for (int j = 1; j <= m; ++j) { // 遍历所有边,判断是否能更新
int a = e[j].a, b = e[j].b, c = e[j].c;
dist[b] = min(dist[b], backup[a]+c);
}
}
return ;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) dist[i] = MAXN;
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
bellman_ford();
if (dist[n] >= MAXN / 2) puts("impossible");
else printf("%d\n", dist[n]);
return 0;
}
3.5.3 SPFA（Bellman-Ford-Moore）算法
3.5.3.1 SPFA 求最短路
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，边权可能为负值，保证不存在负环。请你求出 \(1\) 号点到 \(n\) 号点的最短距离，若无法到达则输出 impossible.
\(1\le n, m\le 10^5\)。
思路：
SPFA 其实就是队列优化的 Bellman-Ford 算法。在 Bellman-Ford 算法中，我们可以发现我们并不需要进行过多的松弛操作，所以我们可以用一个队列保存可能会进行松弛操作的点并进行更新。其最坏复杂度为 \(O(nm)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10, MAXN = 2e9;
typedef pair<int, int> pii;
int n, m;
bool st[N];
int dist[N];
int h[N], e[N], ne[N], w[N], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa() {
queue<int> q;
q.push(1);
st[1] = 1;
dist[1] = 0;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = 0; // 由于存在负权边,可能导致重复入队
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]) q.push(j), st[j] = 1;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1, dist[i] = MAXN;
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
if (dist[n] == MAXN) puts("impossible");
else printf("%d\n", dist[n]);
return 0;
}
3.5.3.2 SPFA 判断负环
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，边权可能为负值。请你判断图中是否存在负权回路。
\(1\le n\le 2000,1\le m\le 10^4\)。
思路：
我们可以定义一个超级源点 \(0\) 号节点，并由其向每个点连一条边权为 \(0\) 的边。那么原图有负环等价于新图有负环，相反地，新图有负环也等价于原图有负环。那么我们可以以超级源点为起点做一次 SPFA（相当于初始时将所有点加入队列），并定义 \(cnt_i\) 表示从 \(0\rightarrow i\) 中经过的路径长度。每一次松弛时，若 \(dis(j)>dis(t)+w(t,j)\)，则同时更新 \(cnt_j=cnt_t+1\)。 若存在某一点 \(u\) 使得 \(cnt_u\ge n\)，说明从 \(0\rightarrow u\) 的最短路长度经过了 \(\ge n\) 条边，即经过了 \(\ge n+1\) 个点。由抽屉原理， 必定有两个点的标号相同，说明图中存在负环。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 1e4+10, MAXN = 2e9;
int n, m;
bool st[N];
int dist[N], cnt[N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {
queue<int> q;
for (int i = 1; i <= n; ++i) q.push(i), st[i] = 1;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = 0;
if (cnt[t] >= n) return 1; // 若最短路经过了>=n条边,说明存在负环
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];
cnt[j] = cnt[t] + 1;
if (!st[j]) q.push(j), st[j] = 1;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1;
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return 0;
}
3.5.4 Floyd 算法
题目：给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环，边权可能为负数，图中不存在负权回路。再给定 \(k\) 个询问，每个询问包含两个整数 \(x\) 和 \(y\)，输出 \(x\) 到 \(y\) 的最短路径长度，如果路径不存在，则输出 impossible。
思路：
Floyd 算法的本质是 dp. 定义 \(f_{k,i,j}\) 表示只经过 \(1\sim k\) 号点，从 \(i\) 号点到 \(j\) 号点的最短路径长度。
考虑其 base case：显然 \(f_{0,i,j}\) 为 \(i\) 到 \(j\) 的边权长度，或 \(0\)（\(i=j\) 时），或 \(+\infty\)（\(i,j\) 没有边相连时）。而 \(i\rightarrow j\) 的最短路径长度显然为 \(f_{n,i,j}\)。
接下来考虑转移方程。对于 \(f_{k,i,j}\)，我们可以将其分解为两个部分：经过 \(k\) 号点和不经过 \(k\) 号点。由于经过 \(k\) 号点的最短路径为 \(f_{k-1,i,k}+f_{k-1,k,j}\)（即 \(i\rightarrow k\) 的最短路径加上 \(k\rightarrow j\) 的最短路径），不经过 \(k\) 号点的最短路径为 \(f_{k-1,i,j}\)，那么转移方程即为：
\[f_{k,i,j}=\min(f_{k-1,i,k}+f_{k-1,k,j},f_{k-1,i,j})\tag{3.4} \]可以证明 dp 的第一维 \(k\) 可以省略，即转移方程 \((3.3)\) 可进一步简化为：
\[f_{i,j}=\min(f_{i,k}+f_{k,j},f_{i,j})\tag{3.5} \]其中，\(f_{i,j}\) 表示从 \(i\) 到 \(j\) 的最短路长度。
Floyd 算法的时间复杂度为 \(O(n^3)\)，空间复杂度为 \(O(n^2)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 210, MAXN = 1e8;
int n, m, k;
int f[N][N];
void floyd() {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
f[i][j] = (i == j) ? 0 : MAXN;
}
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
f[a][b] = min(f[a][b], c);
}
floyd();
while (k -- ) {
int a, b;
scanf("%d%d", &a, &b);
if (f[a][b] >= MAXN/2) puts("impossible");
else printf("%d\n", f[a][b]);
}
return 0;
}
3.6 最小生成树算法
最小生成树：对于一个边带权的无向图 \(G=(V,E)\)，其中 \(V\) 代表图中点的集合，\(E\) 代表图中边的集合，\(n=|V|,m=|E|\)。 由 \(V\) 中全部 \(n\) 个结点和 \(E\) 中 \(n-1\) 条边构成的一个无向连通子图被称为 \(G\) 的一棵生成树。其中边权之和最小的生成树被称为无向图 \(G\) 的最小生成树。
3.6.1 Prim 算法
题目：给定一个 \(n\) 个点 \(m\) 条边的无向图，求出其最小生成树的所有边权之和，若不在则输出 impossible. 图中可能存在重边和自环，边权可能为负数。
\(1\le n\le 500,1\le m\le 10^5\)。
思路：
Prim 算法采用类似朴素 Dijkstra 算法的思想，从一个结点开始，每次选择一个离当前最小生成树最小的结点，将其加入最小生成树，并用这个点的边更新其他结点的距离。
朴素 Prim 算法的时间复杂度是 \(O(n^2)\) 的。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510, MAXN = 2e9;
int n, m;
int g[N][N];
bool st[N];
int dist[N];
int prim() {
for (int i = 1; i <= n; ++i) dist[i] = MAXN;
dist[1] = 0;
int sum = 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] == MAXN) return MAXN; // 如果所有点都无法被更新返回0
st[t] = 1;
sum += dist[t];
for (int j = 1; j <= n; ++j) dist[j] = min(dist[j], g[t][j]); // 更新所有点到最小生成树的距离
}
return sum;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
g[i][j] = MAXN;
}
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == MAXN) puts("impossible");
else printf("%d\n", t);
return 0;
}
3.6.1 Kruscal 算法
模板：AcWing 859. Kruskal算法求最小生成树
题目：给定一个 \(n\) 个点 \(m\) 条边的无向图，求出其最小生成树的所有边权之和，若不在则输出 impossible. 图中可能存在重边和自环，边权可能为负数。
\(1\le n\le 10^5,1\le m\le 2\times 10^5\)。
思路：
Prim 算法是每次选择离当前最小生成树距离最小的点加入最小生成树，而 Kruscal 算法则是每次选择当前边权最小边加入最小生成树。
首先将所有边按边权排序，然后我们用并查集维护一个森林，每次选择目前边权最小的边 \((u,v)\)，若 \(u,v\) 已经在一个连通块内则跳过，否则将 \(u,v\) 两点所在的集合合并，直到选出 \(n-1\) 条边为止。时间复杂度 \(O(m\log m)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10, MAXN = 2e9;
int n, m;
int p[N];
struct Edge {
int a, b, c;
} edges[N*2];
bool cmp(Edge a, Edge b) {
return a.c < b.c;
}
int find(int u) {
if (p[u] != u) p[u] = find(p[u]);
return p[u];
}
void merge(int u, int v) {
int fu = find(u), fv = find(v);
if (fu == fv) return ;
p[fu] = fv;
}
int kruscal() {
int sum = 0, cnt = 0;
for (int i = 1; i <= m && cnt < n-1; ++i) {
int u = edges[i].a, v = edges[i].b, w = edges[i].c;
if (find(u) == find(v)) continue; // 如果两个结点已经在最小生成树中则跳过
merge(u, v), sum += w, cnt ++; // 否则将它们加入最小生成树
}
if (cnt != n-1) return MAXN;
return sum;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) p[i] = i;
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].c);
sort(edges+1, edges+m+1, cmp); // 将边按照边权从小到大排序
int t = kruscal();
if (t == MAXN) puts("impossible");
else printf("%d\n", t);
return 0;
}
3.7 二分图
二分图的定义：若一个无向图中的节点可被划分为 \(U,V\) 两个集合，且各集合之内的点没有边相连，则称这个图为一个二分图。
如图 \(\texttt{3-3}\) 所示，这是一个二分图（\(U=\{1,2\},V=\{3,4\}\)）。
二分图的匹配：给定一个二分图 \(G\)，在 \(G\) 的一个子图 \(M\) 中，\(M\) 的边集 \(E\) 中的任意两条边都不依附于同一个顶点，则称 \(M\) 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一种被称为二分图的最大匹配，其边数即为最大匹配数。
3.7.1 染色法判断二分图
题目：给你一个 \(n\) 个点 \(m\) 条边的无向图，判断其是否是一个二分图。\(1\le n,m\le 10^5\)。
思路：
对于每个连通块，我们可以将其染成黑白二色（即打上 \(0\) 或 \(1\) 的标记），若对于每一条边，其连接的两点均为黑白二色，说明这个图是一个二分图。在打标记的过程中，若一个点被染成了两种颜色，说明该图不是二分图。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<bool, int> pii;
const int N = 1e5+10, M = 2e5+10;
int n, m; bool ans = 1;
bool st[N], col[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool color(int i) {
queue<pii> q;
q.push({0, i});
st[i] = 1;
while (q.size()) {
auto t = q.front();
q.pop();
int u = t.second; bool c = t.first;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) q.push({!c, j}), st[j] = 1, col[j] = !c; // 染色
else if (col[j] == c) return 0; // 若染上两种色说明不是二分图
}
}
return 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) h[i] = -1;
for (int i = 1; i <= m; ++i) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
for (int i = 1; i <= n; ++i) {
if (!st[i]) {
ans &= color(i);
if (!ans) break;
}
}
if (ans) puts("Yes");
else puts("No");
return 0;
}
3.7.2 匈牙利算法
题目：给定一个包含 \(m\) 条边的二分图，其两侧部分分别包含 \(n_1,n_2\) 个点，求出该二分图的最大匹配数。\(1\le n_1,n_2\le 500,1\le m\le 10^5\)。
思路：我们可以将题意转化为这样一种情形：有 \(n_1\) 个男生和 \(n_2\) 个女生，其中有 \(m\) 个人之间互相有好感。求出最多能撮合成的情侣数量。
如图 \(\texttt{3-4}\)，有 \(5\) 个男生和 \(4\) 个女生。我们可以模拟一下：
- 1 号男生和 6 号女生匹配；
- 由于 6 号女生被 1 号男生匹配了，所以 1 号男生匹配 7 号女生，2 号男生匹配 6 号女生；
- 由于 6 号女生被 2 号男生匹配了，所以 1 号男生匹配 7 号女生，2 号男生匹配 9 号女生，3 号男生匹配 6 号女生；
- 4 号男生和 8 号女生匹配；
- 5 号男生无人可以匹配，结束。
也就是说，我们循环 \(n\) 轮，第 \(i\) 轮尝试给 \(i\) 号男生分配一个女生。我们可以用 \(match_i\) 表示 \(i\) 号女生当前匹配到的男生，\(st_i\) 表示 \(i\) 号女生在当前这一轮中是否有被匹配。在第 \(i\) 轮中，我们遍历与 \(i\) 号男生有关系的所有女生，如果 \(j\) 号女生在当前轮中已经分配了男朋友，即 \(st_j=1\)，则跳过；若该女生之前都没有被匹配过或她原来的男朋友可以找一个新的女朋友（可以通过递归实现），则将该女生匹配给 \(i\) 号男生，即 \(match_j=i\)。 时间复杂度 \(O(n_1^2n_2)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
const int N = 510, M = 1e5+10;
int n1, n2, m;
int match[N]; // match[i]表示i号女生当前匹配到的男生
bool st[N]; // st[i]表示在目前这一轮i号女生是否匹配
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool find(int u) { // find(u)返回在第u轮中是否能增加新的匹配数量
for (int i = h[u]; i != -1; i = ne[i]) { // 遍历与u号男生有关系的所有女生
int j = e[i];
if (st[j]) continue; // 如果该女生已经有男朋友了,则直接跳过
st[j] = 1;
if (!match[j] || find(match[j])) {
// 如果该女生目前没有男朋友或她原来的男朋友可以找一个新女朋友
match[j] = u;
return 1;
}
}
return 0;
}
int main() {
scanf("%d%d%d", &n1, &n2, &m);
for (int i = 1; i <= n1; ++i) h[i] = -1;
while (m -- ) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
int ans = 0;
for (int i = 1; i <= n1; ++i) {
for (int i = 1; i <= n2; ++i) st[i] = 0;
bool check = find(i);
if (check) ans ++;
}
return 0;
}