Chapter 3 搜索与图论

知识

模板

1. DFS

我个人的倾向是 “入口初始值是合法的” + “出口判断值是 出界的”

// 排列数字

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 7+3;

int a[maxn];       // 装输出答案
int visited[maxn]; // 是否访问过
int n;

void dfs(int u) // 枚举到了第u位
{
    if (u==n+1) { // 出口: "出界的"
        for (int i=1; i<=n; i++) cout << a[i] << " ";
        puts("");

        return;
    }

    for (int i=1; i<=n; i++)
    {
        if (!visited[i])
        {
            a[u] = i;
            visited[i] = 1;
            dfs(u+1);
            visited[i] = 0;
        }
    }
}

int main()
{
    cin >> n;

    dfs(1); // 入口: "合法的"

    return 0;
}

// n皇后

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 11;

char q[N][N]; // 存储棋盘
bool dg[N * 2], udg[N * 2], cor[N]; // 点对应的两个斜线以及列上是否有皇后

int n;

void dfs(int r)
{
    // 出口: "出界的"
    if (r == n+1) // 放满了棋盘，输出棋盘
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++) cout << q[i][j];
            puts("");
        }
        puts("");
        return;
    }

    for (int i = 1; i <= n; i++) // 对于第 r 行, 考察第 i 列 是否放皇后
    {
        if (!cor[i] && !dg[i + r] && !udg[n - i + r]) // 不冲突，放皇后
        {
            q[r][i] = 'Q';
            cor[i] = dg[i + r] = udg[n - i + r] = 1;

            dfs(r + 1);

            // 恢复现场
            cor[i] = dg[i + r] = udg[n - i + r] = 0;
            q[r][i] = '.';
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            q[i][j] = '.';

    dfs(1); // 入口: "合法的"

    return 0;
}

2. BFS

if 边权 全为1, 则自带“最短路”性质. 个人习惯是直接使用 queue 的模板进行 "洪泛"

基础模板:

// psudo code

// 元素定义
struct node {
    int x, y;
    // ...
};

// queue初始化
init(queue);

// void bfs()
while(!queue.empty())
{
    type qhead = queue.top();
    queue.pop();

    // 扩展 qhead: ...

    queue.push({xx, yy});
}

例题: 走迷宫

// 上下左右 走迷宫 求min_dist

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct node {
    int x, y;
};

const int N = 110;

int n, m;
int g[N][N]; // 地形
int d[N][N]; // 每个点到出发点的距离
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int bfs() 
{
    queue<node> q;

    q.push({1, 1}); // 起点入队

    while(!q.empty())
    {
        auto t = q.front();      // 取队头元素
        q.pop();                 // 队头元素弹出

        for (int i = 0; i < 4; i++) // 队头元素扩展
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];

            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !g[xx][yy] && d[xx][yy] == 0x3f3f3f3f)
            {
                d[xx][yy] = d[t.x][t.y] + 1;
                q.push({xx, yy}); // (x,y) 进队
            }
        }
    }

    return d[n][m];
}

int main() 
{
    cin >> n >> m;

    // 地形输入
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    // 初始化
    memset(d, 0x3f, sizeof d);
    d[1][1] = 0;

    // queue洪泛bfs
    bfs();

    cout << d[n][m] << endl;
    return 0;
}

3. 树和图的 存储 / 遍历 + 拓扑排序

(1) 存储:

• 邻接表: 见下
• 邻接矩阵: omitted

// 开设空间:
const int N = 1e5 + 10; // 点的数据量max是1e5
const int M = 2 * N;    // 以有向图的格式存储, 所以每个节点至多对应2*(n-1)条边

// 邻接表: 完全等同于前面讲过的 head[] (HASH表)
int h[N], e[N], ne[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化:
memset(h, -1, sizeof(h));

// 有向边:
add(a, b);

// 无向边:
add(a, b);
add(b, a);

(2) 遍历:

// dfs 框架
void dfs(int u) {
    st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j=e[i];
        if (!st[j]) {
            dfs(j);
        }
    }
}

// bfs 框架
struct node {
    int x, y;
    // ...
};

void bfs() {
    queue<int> q;

    init();

    while (!q.empty()) {
        int t = q.front(); // 队头出队, 找该点能到的点
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i]; // 通过索引i得到t能到的节点编号

            if (!st[j]) {
                // 扩展 qhead: ...                
                q.push(j);
            }
        }
    }
}

dfs模板: 树的重心

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx;
int n;
int ans = N;

bool st[N]; //记录节点是否被访问过，访问过则标记为true

void add(int a, int b) // nodeA 后插 nodeB
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 以u为根的子树中节点的个数, 包括nodeU
int dfs(int u) 
{
    int res = 0;  //存储 删掉某个节点之后, 最大的连通子图节点数
    st[u] = true; //标记 访问过u节点
    int sum = 1;  //存储 以u为根的树 的节点数

    // 访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);    // u节点的单棵子树节点数
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s;          // 以j为根的树 的节点数
        }
    }

    res = max(res, n - sum); // 选择u节点为重心 最大的 连通子图节点数
    ans = min(res, ans);     // 遍历过的假设重心中 最小的最大联通子图的 节点数
    return sum;
}

int main() 
{
    cin >> n;

    // 初始化
    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i++) 
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); // 无向图
    }

    dfs(1); // 本题可任意选定一个节点开始 u<=n

    cout << ans << endl;
    return 0;
}

bfs模板: 图中点的层次

#include<iostream>
#include<queue>
#include <cstring>
using namespace std;

const int maxn = 1e5+10;

int n, m;
int h[maxn], e[maxn], ne[maxn], idx;
bool st[maxn];  // 访问数组, 防止重复访问
int dist[maxn]; // 维护起点到每个点的min_dist

queue<int> q;

void add(int a, int b) // "idx=a的node" 指向 "值为b的node"
{
    // a -> b
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void bfs()
{
    q.push(1);
    dist[1] = 0;
    st[1] = true; // 访问完, 记得打标记防止重复

    while(!q.empty()) {
        int qhead = q.front();
        q.pop();

        for (int i = h[qhead]; i != -1; i = ne[i])
        {
            int j = e[i]; // i: global_idx | j: node_idx

            // 扩展:
            if (!st[j]) {
                dist[j] = dist[qhead] + 1;
                q.push(j);
                st[j] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));

    // 建边
    for (int i=1; i<=m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    bfs();

    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) <<endl;

    return 0;
}

(3) 拓扑排序:

啥是拓扑排序:

• 一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边
• 一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序

操作:

1. 记录各个点的入度
2. 将入度为 0 的点放入队列
3. 将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同时边的另一侧的点的入度 -1
4. 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

int e[N],ne[N],h[N],idx;
int d[N];
int n, m, top[N], cnt = 0;

vector<int> ans_vec;

// e, ne, h, idx 邻接表模板
// d 代表每个元素的入度
// top 是拓扑排序的序列 (装topo_sort的结果数组)

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool topsort()
{
    queue<int> q;
    int t;
    for (int i = 1; i <= n; i++) // 将所有入度为0的点加入队列
        if (d[i] == 0) q.push(i);

    while(!q.empty())
    {
        t = q.front(); // 取出队首
        ans_vec.push_back(t);  // 加入到 拓扑序列中
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            // 遍历 t 点的出边
            int j = e[i];
            d[j] --; // j 的入度 --
            if (d[j] == 0) q.push(j); // 如果 j 入度为0, 则加入队列当中
        }
    }

    if (ans_vec.size() < n) return 0;
    else return 1;
}

int main()
{
    int a, b;
    cin >> n >> m;

    // 初始化 (链表)
    memset(h, -1, sizeof h);

    for (int i=1; i<=m; i++)
    {
        cin >> a >> b;
        add(a,b);
        d[b] ++; // a -> b, b 的入度++
    }

    if (topsort() == 0) cout << "-1" <<endl;
    else
    {
        for (auto i: ans_vec) cout << i << " ";
    }
    return 0;
}

• 最短路问题
  • 单源最短路:
    • 所有边权值都>0:
      • 朴素 dijkstra: \(O(n^2)\). 适合稠密图
      • 堆优化版 dijkstra: \(O(mlogn)\). 适合稀疏图
    • 存在负权边:
      • Bellman-Ford: \(O(nm)\). 有负环也可以做
      • SPFA: \(O(m) - O(nm)\). 有负环则不能做
  • 多源汇最短路:
    • Floyd: \(O(n^3)\)
• 最小生成树
  • Prim
    • 朴素Prim: \(O(n^2)\). 适合稠密图
    • 堆优化Prim: \(O(mlogn)\). 不咋用...
  • Kruskal: \(O(mlogm)\). 适合稀疏图
• 二分图
  • 染色法: \(O(m+n)\)
  • 匈牙利算法: \(O(m \times n)\). 这是理论值, 实际数字远小于它

TL; DR

(1) 最短路问题:

Dijkstra-朴素 O(n^2)
    初始化距离数组, dist[1] = 0, dist[i] = inf;
    for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
    将不在S中dist_min的点->t
    t->S加入最短路集合
    用t更新到其他点的距离

Dijkstra-堆优化 O(mlogm)
    利用邻接表，优先队列
    在priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > heap;中将返回堆顶
    利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_ford O(nm)
    注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
    初始化 dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
    松弛k次，每次访问m条边

Spfa O(n)~O(nm)
    利用队列优化仅加入修改过的地方
    for k次
        for 所有边利用宽搜模型去优化 bellman_ford 算法
    更新队列中当前点的所有出边

Floyd O(n^3)
    初始化d
    k, i, j 去更新 d

(2) 最小生成树:

Prim: 
    完全类似dijkstra
    只是这里dist[]维护的是每个点到 "集合" 的min_dist

Kruskal:
    所有edges按权值从小到大排序
    并查集 -> 考察如何建边

(3) 二分图:
    判定: 染色法
    最大匹配: 匈牙利算法

注意细节: 如何处理 “重边” 和 “自环”

// (1) 邻接矩阵 g[i][j]
g[i][i] = 0; // handle 自环
g[i][j] = min(g[i][j], w); // handle 重边

// (2) 邻接表 h[i]
void add(int a, int b, int c) // index=a的node --c--> 值=b的node
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

1. dijkstra 算法

单源最短路 + 所有边的权值必须都>0

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1

// 朴素版dijkstra: 适合稠密图 - 邻接矩阵 g[i][j]

// g[i][j] 维护每个node和edge

#include <iostream>
#include <cstring>
using namespace std;

const int N = 500+10, M=1e5+10;

int g[N][N];
bool st[N];  // 是否已经"算过"
int dist[N]; // 每个点到起点到min_dist

int n, m;

void dijkstra()
{
    // 初始化 起点
    dist[1] = 0;

    for (int i=1; i<=n; i++)
    {
        int t = -1; // i 选择连接的 candidate

        for (int j=1; j<=n; j++)
        {
            if (!st[j]) // 如果还没被算过
            {
                if (t==-1 or (dist[j] < dist[t]))
                {
                    t = j; // 在"还没算过"的集合里选择distance_min者
                }
            }
        }

        // 现在已经知道t是谁了. 访问之
        st[t] = true;

        // 更新 "三角不等式"
        for (int j=1; j<=n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);

    // 建边
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;

        // 去重边
        g[x][y] = min(g[x][y], z);
    }

    dijkstra();

    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) <<endl;
    return 0;
}

// 堆优化版dijkstra: 适合稀疏图 - 邻接表 h[i]
// review一下: "基础数据结构" 中 如何给struct定义的类型 维护大根堆/小根堆

// struct 维护每个node

#include<iostream>
#include<queue>
#include <cstring>
using namespace std;

const int maxn = 150000 + 10;

struct node {
    int ve;   // 顶点
    int dist; // 距离出发点的min_dist

    // 结构体 + 小根堆
    bool operator>(const node& other) const {
        return dist > other.dist;
    }
};

int h[maxn], e[maxn], ne[maxn], idx;
int n, m;

int w[maxn];    // 边权
bool st[maxn];  // 点是否被"算过"
int dist[maxn]; // 每个点到出发点的dist_min

void add(int a, int b, int c) // index=a的node --c--> 值=b的node
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra()
{
    // 初始化 "起点"
    dist[1] = 0;

    // 用来筛选 "没被算过"的点集合 中的 dist_min
    priority_queue<node, vector<node>, greater<node>> min_heap;

    min_heap.push({1, dist[1]}); // 起点入队

    while(!min_heap.empty())
    {
        // 取 队首元素
        auto top = min_heap.top();
        min_heap.pop();

        int cur_idx = top.ve;
        int cur_dst = top.dist;

        // 算过就不考虑了
        if (st[cur_idx]) continue;

        // 现在这个top就是 "没被算过"的点集合 中的 dist_min者 了
        st[cur_idx] = true;

        for (int i=h[cur_idx]; i!=-1; i=ne[i])
        {
            int j = e[i]; // cur_idx -> j

            if (dist[j] > cur_dst + w[i]) {
                dist[j] = cur_dst + w[i];
                min_heap.push({j, dist[j]});
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);

    // 建边
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        // 有重边也不要紧, 可以handle
        add(x, y, z);
    }

    dijkstra();

    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) << endl;
    return 0;
}

2. Bellman-Ford

有边数限制的最短路, 对边权值没有要求, 甚至有负环也可以做

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible

注意：图中可能 存在负权回路

注意, 一定要开 back[] 数组进行备份

如果在本轮循环中，我们先用边 (x, a) 更新了 dist[a]，使其变短。
接着，在处理边 (a, b) 时，就会立即使用这个 刚刚被更新过 的 dist[a]来尝试更新 dist[b]。
这就导致在 同一轮迭代 中，源点到 b 的路径一下子经过了 (x, a) 和 (a, b) 两条边，这违反了 Bellman-Ford 算法 “每轮迭代最多将最短路径增加一条边” 的核心思想

通过使用 back 数组，dist[b] = min(dist[b], back[a] + w); 确保了所有更新都基于上一轮的状态，保证了算法的正确性:

for (int i = 0; i < k; i ++ )
{
    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], backup[a] + w);
    }
}

代码:

// struct 维护 a---weight--->b

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge { // 把每个边保存下来即可
    int a;
    int b;
    int w;
} e[M];

int dist[N];
int back[N]; // 备份数组防止串联
int n, m, k; // k代表最短路径最多包含k条边

void bellman_ford() 
{
    // 初始化 "起点"
    dist[1] = 0;

    for (int i = 1; i <= k; i++) 
    {
        // copy cur_dist[] into back[]
        memcpy(back, dist, sizeof dist);

        // 遍历所有边
        for (int j = 1; j <= m; j++) 
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;

            // 使用backup: 避免给a更新后立马更新b
            dist[b] = min(dist[b], back[a] + w);
        }
    }
}

int main() 
{
    cin >> n >> m >> k;

    // 初始化
    memset(dist, 0x3f, sizeof dist);

    // 建边
    for (int i = 1; i <= m; i++) 
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}

3. SPFA

(1) SPFA 求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible

数据保证 不存在负权回路

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N=1e5+10;

#define fi first
#define se second

typedef pair<int,int> PII; // 到源点的距离，下标号

int h[N],e[N],w[N],ne[N],idx;
int dist[N]; // 各点到源点的距离
bool st[N];
int n,m;
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa()
{
    queue<PII> q;

    // 初始化 "起点"
    dist[1]=0;
    st[1]=true;

    q.push({0,1}); // 起点 入队

    while (!q.empty())
    {
        auto p = q.front();
        q.pop();

        int t = p.se;
        st[t] = false; // 从队列中取出来之后该节点st被标记为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])
                {
                    st[j]=true;
                    q.push({dist[j],j});
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);

    // 建边
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c);
    }

    spfa();

    if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}

总结复盘一下:

[!tip] 为什么BF可以做负环，但是SPFA不能做 Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；

但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环

[!tip] BF && SPFA 终止条件为什么不一样 Bellman_ford算法里最后 return -1 的判断条件写的是 dist[n]>0x3f3f3f3f/2; 而spfa算法写的是 dist[n]==0x3f3f3f3f;

其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的 0x3f3f3f3f

[!tip] Dijkstra vs. SPFA

Dijkstra: 本质上是贪心! 这个贪心策略成立的前提是图中没有负权边。因为没有负权边，所以你一旦确定了一个最近的点，就不可能再通过一个更远的点绕回来

SPFA: 它不相信任何一次的距离是“最终”的，除非算法自然结束。一个节点的距离可以被反复更新（松弛）。正因为它可以处理负权边。一条负权边的存在，完全可能让一个之前看起来“很远”的节点，突然变成一个“中转捷径”，从而更新其他节点的距离，即使那些节点之前已经被访问过。

(2) SPFA 求负环

给定一个 n 个点 m 条边的有向图, 图中 可能存在重边和自环, 边权可能为负数

请你判断图中是否存在负权回路

[!tip] 设计思路

每次更新时: - dist[j] = dist[t] + w[i]; - cnt[j] = cnt[t] + 1;

当 cnt[x] >= n时，说明x这形成了一个负环 (n边 -> n+1点 -> 抽屉原理)

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int N = 2e3 + 10, M = 1e4 + 10;

int n, m;
int head[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int cnt[N]; // cnt[x] 表示 当前从1-x的最短路的边数

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx++;
}

bool spfa()
{
    queue<int> q;

    // 不仅仅是1了, 因为点1可能到不了有负环的点, 因此所有点都入队
    for (int i=1;i<=n;i++)
    {
        q.push(i);
        dist[i] = 0;
        st[i] = true;
    }

    while (!q.empty())
    {
        int t = q.front();
        q.pop();

        // 从队列中取出来之后该节点st被标记为false, 代表之后该节点如果发生更新可再次入队
        st[t] = false;

        for (int i=head[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 (cnt[j] >= n) return true;
                // 当前已经加入队列的结点, 无需再次加入队列
                // 即便发生了更新也只用更新数值即可, 重复添加降低效率
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(head, -1, sizeof head);
    memset(dist, 0x3f, sizeof dist);

    // 建边
    for (int i = 1; i <= m; i++) 
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

4. Floyd

给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环 ，边权可能为负数

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible

数据保证图中 不存在负权回路

#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[N][N];

void floyd() 
{
    for (int k = 1; k <= n; k++) // 注意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]); // 纯暴力三角不等式
}

int main() 
{
    cin >> n >> m >> k;

    // 初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) d[i][j] = 0; // handle 自环
            else d[i][j] = INF;

    while (m--) 
    {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z); // handle 重边
    }

    floyd();

    while (k--)
    {
        cin >> x >> y;

        if (d[x][y] > INF/2) puts("impossible"); // 由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

5. Prim

适合 稠密图

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N]; // dist[i]: 每个点到"集合"的距离
bool st[N];  // st[i]:   每个点是否已访问

int prim()
{
    int res = 0; // res: 最小生成树的树边权重之和
    for (int i = 0; i < n; i ++ )
    {
        int t = -1; // t: 在"集合"外, 要被连接的点

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // t: 在"集合"外, 距离"集合"最近的点

        if (i && dist[t] == INF) return INF; // 注意不能是起点啊

        if (i) res += dist[t];
        st[t] = true; // t 算是访问完毕了

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    cin >> n >> m;

    // 初始化
    memset(g, 0x3f, sizeof g);
    memset(dist, 0x3f, sizeof dist);

    // 建边
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        // 无向边 + 重边
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

6. Kruskal

适合 稀疏图

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge {
    int a, b, w;
}edges[M];

bool cmp(Edge x, Edge y) // 辅助sort的回调函数
{
    return x.w < y.w;
}

int find(int x) // 并查集辅助函数
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    // (1) 将所有edge按权值从小到大的顺序sort
    sort(edges, edges + m, cmp);

    // 初始化并查集
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // (2) 操作: if a 和 b 不在一个集合 (已做/未做), 则建边, 并merge
    int res = 0, cnt = 0; // res: 权重之和 cnt: 建立的边数
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        // 找root -> 判定是否在同一集合
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b; // merge
            res += w; // 建边
            cnt ++ ;  // 边数统计
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

7. 二分图判定 / 最大匹配

定义:

有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接

示意:

(1) 染色法 - 二分图判定

1. 开始对任意一未染色的顶点染色
2. 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色
3. 若已经染色且颜色和相邻顶点的颜色相同，则说明不是二分图，若色不同则继续判断

bfs 和 dfs 可以搞定, 模板给的是dfs

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 * 2;

int e[N], ne[N], idx;
int h[N];
int color[N]; //保存各个点的颜色: 0 未染色，1 是红色，2 是黑色
int n, m;

void add(int a, int b) // 邻接表插入点和边
{
    e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}

bool dfs(int u, int c) // 给 nodeU 染 c 色 (c = 1 || 2)
{
    color[u] = c; // u的点成 c 染色

    // 遍历和 u 相邻的点
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];                   
        if (!color[b]) // 相邻的点没有颜色, 则递归处理这个相邻点
        {
            if(!dfs(b, 3 - c)) return false;
            //（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）
            //（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）
        }
        else if (color[b] && color[b] != 3 - c)
        { 
            // 如果已经染色，判断颜色是否为 3 - c
            return false; // 如不是，说明冲突，返回
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;

    // 初始化
    memset(h, -1, sizeof h);

    // 建边
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); // 无向边
    }

    for(int i = 1; i <= n; i++)
    {
        if (!color[i]) // 如果没染色
        {
            if (!dfs(i, 1)) // 染色该点，并递归处理和它相邻的点
            {
                cout << "No" << endl; // 出现矛盾，输出NO
                return 0;
            }
        }
    }

    cout << "Yes" << endl;//全部染色完成，没有矛盾，输出YES
    return 0;
}

(2) 匈牙利算法 - 二分图最大匹配

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

void add(int a , int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int find(int x)
{
    // 遍历自己喜欢的女孩
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) // 如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true; // 那x就预定这个女孩了
            // 如果女孩j没有男朋友, 或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    // 自己中意的全部都被预定了。配对失败。
    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;

    // 初始化
    memset(h, -1, sizeof h);

    while (m--)
    {
        int a,b;
        cin >> a >> b;
        add(a, b);
    }


    int res = 0;
    for (int i = 1; i <= n1; i ++)
    {  
        // 因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
        memset(st,false,sizeof st);
        if (find(i)) res++;
    }  

    cout << res <<endl;
}