前言

本篇介绍算法竞赛中最最重点的一个部分搜索和图论。搜索分为广度优先搜索和深度优先搜索，在题目中非常的常见。而在图论中经常考察的最短路与最小生成树，是算法中极为重要一项基本功。

DFS(暴搜)

可以被称为“2022年度算法”的一款算法，实用价值极高！！！

DFS（深度优先搜索）本质上维护一个隐藏的stack，不具有最短性

空间：O(h)O(h) （较节省空间）

DFS涉及两个重要的概念：

  • 回溯：按代码理解就是需要return的地方
  • 剪枝：提前判断一些肯定不满足条件的方法，并将其直接回溯

注意点：

  • 回溯的过程中注意恢复现场
  • 必然有一个标记访问的过程

全排列数字

将1-n之间的数字全排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

const int N = 10;
int n;

int path[N];
bool st[N];

// u理解为树的层
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
        return;
    }
    
    // 枚举1~n
    for (int i = 1; i <= n; i ++ ) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main() {
    scanf("%d", &n);
    
    dfs(0);
    
    return 0;
}

n-皇后

n-皇后

逐行搜

通过分析题目给出的规则，发现每一行只能出现一个皇后。加上列与对角线的限制，暴搜出所有满足题目的答案

dfs记录行数, 时间复杂度O(n∗n!)O(n*n!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;

const int N = 10;
int n;
char str[N][N];
// 分别记录列、对角线、反对角线
bool col[N], dg[N], udg[N];

// u为行数
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(str[i]);
        puts("");
        return;
    }
    
    for (int i = 0; i < n; i ++ ) {
        // y = x + b -> b = y - x
        // y = -x + b -> b = y + x
        if (!col[i] && !dg[i-u+n] && !udg[i+u]) {
            str[u][i] = 'Q';
            col[i] = true, dg[i-u+n] = true, udg[i+u] = true; //标记
            dfs(u+1);
            col[i] = false, dg[i-u+n] = false, udg[i+u] = false; //还原
            str[u][i] = '.';
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ )
            str[i][j] = '.';
            
    dfs(0);
    
    return 0;
}

逐格搜

dfs同时记录行数，列数，与皇后数， 时间复杂度O(2n2)O(2^{n^2})

每一格仅有两种情况即有皇后和无皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;

const int N = 10;
int n;
char str[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
    // 走到一行的末尾，自动定位至下一行行头
    if (y == n) y = 0, x++;
    
    if (x == n) {
        if (s == n) {
            for (int i = 0; i < n; i ++ ) puts(str[i]);
            puts("");
        }
        return;
    }
    
    // 此格无皇后
    dfs(x, y + 1, s);
    
    // 此格有皇后
    if (!row[x] && !col[y] && !dg[y-x+n] && !udg[y+x]) {
        str[x][y] = 'Q';
        row[x] = true, col[y] = true, dg[y-x+n] = true, udg[y+x] = true;
        dfs(x, y + 1, s + 1);
        row[x] = false, col[y] = false, dg[y-x+n] = false, udg[y+x] = false;
        str[x][y] = '.';
    }
        
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            str[i][j] = '.';
            
    dfs(0, 0, 0);
    
    return 0;
}

BFS

BFS（广度优先搜索）本质上维护一个queue，能够计算最短路

空间：O(2h)O(2^h) （所需要的空间和指数呈指数级别）

BFS记录路径

开辟一个数组，记录每一个点是由哪个点转移而来

但最后输出的结果为倒序

冲出迷宫

image-20220204193443623

BFS

这道除了用到了BFS外，还有两处之前没有掌握的地方

  1. 距离的记录：运用DP动态规划，记录下每一层点到起点的距离
  2. 路径过程的记录：用一个数组记录当前点的前一个点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// BFS
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 记录图
int d[N][N]; // 记录距离的同时标记此点是否已访问
PII q[N*N], path[N][N]; // 模拟队列，记录过程路径
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs() {
    int hh = 0, tt = -1;
    q[++tt] = {1, 1};
    
    memset(d, -1, sizeof d); // 初始化为-1
    d[1][1] = 0;
    
    while (hh <= tt) {
        auto t = q[hh++];
        
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[t.x][t.y] + 1; // *DP记录下每一层的距离
                path[x][y] = t; // *记录下当前点的下一个点
                q[++tt] = {x, y};
            }
        }
    }
    
    return d[n][m];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);
            
    cout << dfs() << endl;
    
    // 反向遍历，得到起点到终点的路径
    int a = n, b = m;
    while (a >= 1 || b >= 1) {
        cout << a << ' ' << b << endl;
        auto t = path[a][b];
        a = t.first, b = t.second;
    }
    
    return 0;
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 110;

int n, m;
int g[N][N]; // 记录图

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int minPath = 1e9;
bool st[N][N];

int dfs(int x, int y, int step) {
    if (x == n && y == m) {
        minPath = min(minPath, step);
        return minPath;
    }
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] == 0 && !st[a][b]) {
            st[x][y] = true; // 标记已访问
            dfs(a, b, step + 1);
            st[x][y] = false; // 恢复现场
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);
            
    dfs(1, 1, 0);
    cout << minPath << endl;
    
    return 0;
}

树与图

树可以被看作一种特殊的图（只有一个根结点）

图的存储方式分别两种：

  • 邻接矩阵：二维数组记录ab ba（无向图同时记录双向），无权重用0-1表示，有权重则记录对应的权重值

  • 邻接表：如下

另，当题目中的数据超过10610^6时，考虑用scanf, printf，以下则不限

邻接表存储

数组模拟邻接表

图中的每个结点都有一个单链表，用于存储该点可以到达的点

1
2
3
4
5
6
7
8
// h[]代表存储了多个结点，与单链表中的head比较记忆
int h[N], e[M], ne[M], idx;

memset(h, -1, sizeof h);

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

遍历

DFS

1
2
3
4
5
6
7
8
9
10
11
bool st[N];

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);
    }
}

树的重心

难理解

树的重心

首先这是比较绕的一道题，可能是我看了这么多算法以来，花了最多时间的一道

不过我大抵碰到了我的一个软肋，树+DFS。不容易理解的一个数据结构加上不易理解的一个算法，而恰恰这样题总是能够以很少的代码，解决很复杂的题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2*N;
int n;
bool st[N];
int h[N], e[M], ne[M], idx;
int ans = N;

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

// 返回以u为根结点子树的结点个数
int dfs(int u) {
    st[u] = true;
    
    // sum:存储 以u为根的树 的节点数，包括u
    // res:存储 删掉某个节点之后，最大的连通子图节点数
    int sum = 1, res = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            int s = dfs(j); // 返回以j为根结点的子树中的结点数，包括其本身
            res = max(res, s); // 比较u结点的每个子树大小，取最大
            sum += s; //计算u结点以下所有子树结点之和，包括u本身
        }
    }
    
    res = max(res, n - sum); // 最大的子树与u结点以上部分作比取最大值
  
    ans = min(ans, res); // 比较得出最大值中的最小值，即为重心
    
    return sum;
}

int main() {
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << ans << endl;
    
    return 0;
}

BFS

在权重为1的情况下，可以用BFS求解最短距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
queue<int> q;
int d[N]; // 存储距离

memset(h, -1, sizeof h);
int dfs() {
    q.push(1);
    
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    while (q.size()) {
        int t = q.front();
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i]) {
            if (d[i] == -1) {
                d[i] = d[t] + 1;
                q.push(i);
            }
        }
    }
    return d[n];
}

拓扑排序

img

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列

如上图，0->1->2->3->4即为拓扑序列。注意拓扑序列并不唯一

时间复杂度：O(n+e)O(n+e)，nn 表示点数，ee 表示边数

搜索入度为零的顶点所需的时间是O(n)O(n)，每个顶点入度减1的运算共执行了ee次，由此得出时间复杂度

  • 有向图才存在拓扑序列
  • 利用BFS实现拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N]; // d[]存储每个点的入度

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

// 核心代码
// 简言之，入度为0就入队，队列的次序即为拓扑序列
bool topsort() {
    int hh = 0, tt = -1;
    
    for(int i = 1; i <= n; i++)
        if (!d[i]) 
            q[++tt] = i; // 找到入度为0的突破口
    
    while (hh <= tt) {
        int t = q[hh++];
        
        // 遍历并修改入度
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (d[j] == 0) q[++tt] = j;
        }
    }
    
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列
    return tt == n-1;
}


int main() {
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b]++; // 入度+1
    }
    
    if (topsort()) {
        // 入队的顺序就是拓扑序
        for(int i = 0; i < n; i++) printf("%d ", q[i]);
        puts("");
    } else puts("-1");
    
    return 0;
}

最短路问题

最短路

单源最短路

从某一点到图上所有点的最短距离

朴素版Dijkstra

边权均为正，体现贪心

时间复杂度：O(n2+m)O(n^2+m)，n个点m条边

适用于稠密图（mm与n2n^2是一个数量级），使用邻接矩阵存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int g[N][N]; // 邻接矩阵
int dist[N];
bool st[N]; // 标记是否已被访问过

memset(g, 0x3f, sizeof g);

int dijkstra() {
    // 初始化距离为正无穷！！
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    /* 有几个点就有几轮循环
     * 每轮选择距离最近的点，去更新其它点
     * 重复n次，就能使得每一个点都被选取到  */
    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;
                
        st[t] = true; // 标记访问
        
        // 用这个距离最近的点，去更新其它的点距离原点的距离
        for(int j = 1; j <= n; j++) 
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        
    }
    // 判断是否可以到达目标点
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

堆优化版Dijkstra

边权均为正

时间复杂度：O(mlogn)O(mlogn)，n点m边

适用于稀疏图，数据结构邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
typedef pair<int, int> PII;

int h[N], e[N], ne[N], w[N], idx; // 带权重的邻接表
int dist[N];
bool st[N]; // 标记是否已被访问过

memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
    heap.push({0, 1}); // (距离，目的点)
    
    while(heap.size()) {
        auto t = heap.top(); 
        heap.pop();
        
        int ver = t.second; // 取出当前距离最小的点
        
        if (st[ver]) continue;
        st[ver] = true;
        
        // 当前距离最小点更新其它距离
        for(int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j}); 
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

Bellman-Ford算法

存在负边

时间复杂度：O(nm)O(nm)

在求解最短路时，如果对所经过的边数有要求，可以使用此算法

在每一轮更新时，需对原始数组进行备份，防止出现此轮才更新的最短距离去更新其它点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dist[N], backup[N];

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

bool bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    // 以规定经过的边数限制循环的总次数
    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); // 利用备份结果更新距离
        }
    }
    
    // 因处于负权图，所以不可直接与无穷判等
    if (dist[n] > 0x3f3f3f3f/2) return false; 
    return true;
}

SPFA算法

SPFA算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。

推荐使用！！！正权图也能过（被卡需换成堆优化Dijkstra）

时间复杂度：O(m)O(m)，最坏情况为O(nm)O(nm)

可以简单理解为运用队列实现的宽搜来优化最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N]; // 标记该点是否在队列中，可先后重复进行队列

memset(h, -1, sizeof h);

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

bool spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true; // 标记这点在队列内
    
    // 核心部分，类似一个BFS的过程
    while (q.size()) {
        int t = q.front();
        q.pop();
        
        st[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]) { // 该点不在队列内
                    q.push(j);
                    st[j] = true;
                }
                
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return false;
    return true;
}

判负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
bool spfa() {
    // memset(dist, 0x3f, sizeof dist);
    // dist[1] = 0;
    
    queue<int> q;
    // q.push(1);
    // st[1] = true;
    
    for(int i = 1; i <= n; i++) {
        st[i] = true;
        q.push(i);
    }
    
    while(q.size()) {
        int t = q.front();
        q.pop();
        
        st[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];
                
                // 核心代码
                cnt[j] = cnt[t] + 1;
                // n个点最多为n-1条边，超出判定为环
                if (cnt[j] >= n) return true;
                
                if (! st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

区别

Dijkstra是基于贪心的思想，每次选择最近的点去更新其它点，过后就不再访问。

而在SPFA算法中，只要有某个点的距离被更新了，就把它加到队列中，让它去更新与它相邻的其它点，所有每个点有被重复加入队列的可能

多源汇最短路

计算任意一点到任意一点的最短距离

Floyd算法

基于动态规划的思想

时间复杂度：O(n3)O(n^3)

状态转移方法：d[k][i][j]=d[k−1][i][k]+d[k−1][k][j]d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];

// Floyd算法核心
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]);
}

int main() {
    scanf("%d%d%d", &n, &m, &Q);
    
    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;
    
    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        
        d[a][b] = min(d[a][b], c); // 保留最小边
    }
    
    floyd();
    
    while(Q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2) puts("impossible");
        else printf("%d\n", d[x][y]);
    }
    
    return 0;
}

最小生成树

最小生成树

Prim

首先选出权重最小的边ab加入集合，接着寻找与a和与b相关联的边，选取其中最小的加入集合。重复这一过程，从已知的点出发寻找最短边，同时要避免成环。最后形成最小生成树

朴素版Prim

联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
memset(g, 0x3f, sizeof g);
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n, m;

int prim() {
    // 初始化所有距离为负无穷
    memset(dist, 0x3f, sizeof dist);
    int res = 0; // 用于记录权重
    // 循环迭代n次，在此写法中，默认选取了第一个点为起点
    for(int i = 0; i < n; i++) {
        int t = -1;
        // 在第一次循环中，默认选取了第一个点
        // 此后每次选取距离集合最近的点
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[j] > dist[t]))
                t = j;
        // 默认跳过第一次循环，从第二点开始即i=1开始计算
        // 遍历结果若为负无穷，说明图不连通
        if (i && dist[t] == INF) return INF; 
        if (i) res += dist[t]; // 将本次最短距离记录到权重
        // 更新其它点到集合的距离
        for(int j = 1; j <= n; j++) 
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true; // 标记访问，避免成环
    }
    return res;
}

Kruskal

依次选择出权重最小，次小，次次小……的边，使所有的点能够关联起来，同时避免成环，得到最小生成树

  1. 将所有边按权重从小到大排序，时间复杂度：O(mlogm)O(mlogm)
  2. 按顺序枚举每条边ab，权重c，时间复杂度：O(m)O(m)，如果ab此前在集合中还不连通，则将这条边加入到集合中（并查集）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int p[N];
struct Edge{
    int a, b, w;
    // 重载小于号，使得按权重从小到大排序
    bool operator< (const Edge& W) const {
        return w < W.w;
    }
} edges[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    // 1. 按权重排序
    sort(edges, edges + m);
    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;
    int res = 0, cnt = 0;
    // 2. 枚举每条边
    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) { // 如果ab不连通
            res += w;
            cnt++;
            p[a] = b; // 使得ab连通，从而避免成环
        }
    }
    // 如果边数与顶点-1不相等，证明图无法连通
    if (cnt < n - 1) return INF;
    else return res;
}

二分图

二分图：将点均匀地分到两边，边在集合之间，集合内部没有边

一个图是二分图，当且仅当图中不含奇数环（环中边为奇数）

染色法

DFS，非常巧妙的一个算法，它的写法值得好好回味

O(n+m)O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 1e5 + 10, M = 2*N;

memset(h, -1, sizeof h); // 当有多组数据时，每次都要初始化

int h[N], e[M], ne[M], idx; 
int color[N];

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; // c为1的时候，转换为2。反之为1
        } else if (color[j] == c) return false; // 如果染色重复(11,22)，则不是二分图
    }
    
    return true;
}

//---------------------------------------------------------

    add(a, b), add(b, a); // 无向图处理方式
    bool flag = false;
    // 这里一定要把所有点遍历一遍，因为图有可能不连通！！！
    // 只从一个点出发会出现不能遍历完的情况
    for(int i = 1; i <= n; i++) 
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag = true;
                break;
            }
        }

    if (flag) puts("impossible");
    else puts("Yes");

AcWing695.劣马

重返天梯-L2-023 图着色问题 (25 分)

匈牙利算法

二分配对算法，“月老算法”。实现均匀分配，某一数有多个配对选项，而另一个数只有一个，为此进行合理分配，实现匹配的最大化，即完全匹配

O(mn)O(mn)，实际运行时间远小于它

劣马 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N = 510, M = 1e5 + 10;

memset(h, -1, sizeof h);

int h[N], e[M], ne[M], idx;
int match[N]; // match[右] = 左：记录右半部匹配的左半部是哪个点
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] == 0 || find(match[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++;
}

参考资料

AcWing算法基础课