C++算法之旅、06 基础篇 | 第三章 图论

常用代码模板3——搜索与图论 - AcWing

DFS

尽可能往深处搜，遇到叶子节点（无路可走）回溯，恢复现场继续走

• 数据结构：stack
• 空间：需要记住路径上的点，O(h)" role="presentation">O(h)$O(h)$。
• ⭐ BFS使用空间少；无最短路性质

每个DFS一定对应一个搜索树；要考虑用什么顺序遍历所有方案；DFS就是递归

剪枝：提前判断当前方案不合法，就不用继续往下走了，直接回溯

842

842. 排列数字 - AcWing题库

highlighter- cpp

#include 
#include 
#include 

using namespace std;

const int N = 10;
int path[N], n;
bool st[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;  // 恢复现场
        }
    }
}

int main() {
    cin.tie(0);
    cin >> n;
    dfs(0);

    return 0;
}

843

843. n-皇后问题 - AcWing题库

搜索顺序、1

每行放一个，直到n行放满，类似全排列

highlighter- cpp

#include 
#include 
#include 

using namespace std;

const int N = 20;  // 对角线个数 2n-1
char g[N][N];
int n;
bool col[N], dg[N], udg[N];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) puts(g[i]);
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}

搜索顺序、2

挨个枚举每个格子，每个格子放与不放

highlighter- cpp

#include 
#include 
#include 

using namespace std;

const int N = 20;  // 对角线个数 2n-1
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
    if (y == n) x++, y = 0;
    if (x == n) {
        if (s == n) {
            for (int i = 0; i < n; i++) puts(g[i]);
            cout << endl;
        }
        return;
    }
    // 不放皇后
    dfs(x, y + 1, s);
    // 放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = '.';
        }
    }
    dfs(0, 0, 0);
    return 0;
}

BFS

一层一层搜（稳重）

• 数据结构：queue
• 空间：需要保存一层的点，O(2h)" role="presentation">O(2h)$O(2^h)$
• ⭐ BFS使用空间多；有最短路性质（前提图所有边权重都为 1）

844

844. 走迷宫 - AcWing题库

d 数组存储每一个点到起点距离

highlighter- cpp

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e2 + 10;
typedef pair<int, int> PII;

int n, m;
int map[N][N], d[N][N];
PII q[N * N];

int bfs() {
    int st = 0, ed = 0;
    q[0] = {0, 0};
    memset(d, -1, sizeof d);
    d[0][0] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (st <= ed) {
        auto t = q[st++];
        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 &&
                d[x][y] == -1) {
                q[++ed] = {x, y};
                d[x][y] = d[t.first][t.second] + 1;
            }
        }
    }
    return d[n - 1][m - 1];
}

int main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> map[i][j];
    cout << bfs();
    return 0;
}

845 ⭐ Airbnb面试

845. 八数码 - AcWing题库

• 状态表示复杂：每个节点相当于3*3矩阵；节点如何存队列里、如何记录距离
  • 可以用字符串保存，使用 unordered_map
• 状态转移
  • 想象成3*3的位置；然后把x移动到4个位置上去判断，再恢复成字符串；难点是二维位置与一维位置间的转换

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;

int bfs(string start) {
    string end = "12345678x";
    queue q;
    unordered_mapint> d;

    q.push(start);
    d[start] = 0;

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    while (q.size()) {
        auto t = q.front();
        q.pop();

        int distance = d[t];
        if (t == end) return distance;

        // 状态转移
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[k], t[a * 3 + b]);
                if (!d.count(t)) {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main() {
    cin.tie(0);
    string start;
    for (int i = 0; i < 9; i++) {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;

    return 0;
}

树与图

有向图、无向图 （特殊的有向图，a->b、b->a）。只需要考虑有向图的存储方式。树是无环连通图

邻接矩阵

不太常用。开二维bool数组 G[A][B] 存储 A->B 的信息，有重边就保留一条（可以是最短边）。空间 O(n2)" role="presentation">O(n2)$O(n^2)$，适合存储稠密图

邻接表 ⭐

常用。每个节点上开一个单链表（类似拉链法哈希表），每个链存储可到的点（次序不重要）。单链表可以数组模拟或vector（效率慢），适合存储稀疏图

DFS 树与图

O(n+m)" role="presentation">O(n+m)$O(n+m)$

846 ⭐⭐

AcWing 846. 树的重心 - AcWing

highlighter- arduino

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;  // 数据范围是10的5次方
const int M = 2 * N;  // 以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N];  // 邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M];   // 存储元素
int ne[M];  // 存储列表的next值
int idx;    // 单链表指针
int n;      // 题目所给的输入，n个节点
int ans = N;  // 表示重心的所有的子树中，最大的子树的结点数目

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

// a所对应的单链表中插入b  a作为根
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

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

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

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

    // n-sum 如图中的n-size值，不包括根节点4；
    res = max(res, n - sum);  // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans);  // 遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;
}

int main() {
    memset(h, -1, sizeof h);  // 初始化h数组 -1表示尾节点
    cin >> n;                 // 表示树的结点数

    // 题目接下来会输入，n-1行数据，
    // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
    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 树与图

O(n+m)" role="presentation">O(n+m)$O(n+m)$

847 ⭐

AcWing 847. 图中点的层次 - AcWing

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, d[N];

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

int bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[1] = 0;
    q.push(1);
    while (q.size()) {
        auto u = q.front();
        q.pop();
        int distance = d[u];
        if (u == n) return distance;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1) {
                d[j] = distance + 1;
                q.push(j);
            }
        }
    }
    return -1;
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs();
    return 0;
}

有向图的拓扑序列

拓扑序列：有向边uv， u在序列中都在v之前

有向无环图被称为拓扑图。有向无环图至少存在一个入度为0的点，所有入度0的点排在最前位置，然后不断删除入度为0的点

848 ⭐

848. 有向图的拓扑序列 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], ne[N], e[N], idx, d[N];

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

void bfs() {
    queue<int> q;
    queue<int> ans;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q.push(i);
    }
    while (q.size()) {
        auto u = q.front();
        ans.push(u);
        q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if (d[j] == 0) q.push(j);
        }
    }
    if (ans.size() != n)
        cout << -1;
    else
        while (ans.size()) {
            cout << ans.front() << " ";
            ans.pop();
        }
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    bfs();
    return 0;
}

最短路

• 单源最短路：单个点到其他所有点最短距离。 （n 点数，m 边数）
  • 所有边权都是正数
    • 朴素Dijkstra：O(n2)" role="presentation">O(n2)$O(n^2)$ 适用于稠密图
    • 堆优化版Dijkstra：O(mlog2n)" role="presentation">O(mlog2n)$O(mlo{g}_{2}n)$ 适用于稀疏图
  • 存在负权边
    • 贝尔曼-福特 Bellman-Ford：O(nm)" role="presentation">O(nm)$O(nm)$
    • 优化贝尔曼-福特 SPFA：一般O(m)" role="presentation">O(m)$O(m)$，最坏O(nm)" role="presentation">O(nm)$O(nm)$
• 多源汇最短路：起点与终点不确定（一对起点终点）
  • 弗洛伊德 Floyd：O(n3)" role="presentation">O(n3)$O(n^3)$

⭐ 考察侧重点是建图，定义点和边

朴素Dijkstra

利用了贪心，每次找最小的

1. 初始化所有点到起点距离：dis[1] = 0，dis[i] = +∞

2. 集合s：存储已经确定最短距离的点

3. for n次

   1. 找到不在 s 中的距离原点最近的点 t

   2. t 加到 s 去

   3. 用 t 更新其他点的距离（从t出去所有边能否更新其他点距离）

      dis[x] > dis[t] + w

849

849. Dijkstra求最短路 I - AcWing题库

稠密图，用邻接矩阵存；最短路问题里面，自环应不存在，重边应只保留距离最短的

highlighter- arduino

#include 
#include 
#include 
#include 

using namespace std;

const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra() {
    // 初始化
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 路径最长n个点
    for (int i = 1; i <= n; i++) {
        // 寻找不在s中的dist最小的点t
        int t = -1;
        for (int i = 1; i <= n; i++) {
            if (!st[i] && (t == -1 || dist[t] > dist[i])) t = i;
        }
        // 将t加入s
        st[t] = true;
        // 更新 dist
        for (int i = 1; i <= n; i++) {
            // if (g[t][i] != 0x3f3f3f3f) {
            dist[i] = min(dist[i], dist[t] + g[t][i]);
            // }
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
    else
        return dist[n];
}

int main() {
    cin.tie(0);
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        // 解决 自环、重边 问题
        if (a != b) g[a][b] = min(g[a][b], c);
    }
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

堆优化Dijkstra

朴素方法中，查找不在 s 中距离原点最近的点共执行 n2" role="presentation">n2$n^2$ 次；更新dis数组相当于遍历了所有边，共执行 m 次；**可以对这两个操作进行堆优化，前者变O(1)∗O(n)=O(n)" role="presentation">O(1)∗O(n)=O(n)$O(1)\ast O(n)=O(n)$，后者变O(log2n)∗O(m)=O(mlog2n)" role="presentation">O(log2n)∗O(m)=O(mlog2n)$O(lo{g}_{2}n)\ast O(m)=O(mlo{g}_{2}n)$ **

堆有两种实现方式：手写堆、优先队列（不支持修改任意一个元素操作，容易冗余）

前者有n个元素，后者可能m个元素；使用优先队列时间复杂度可能变成O(mlog2m)" role="presentation">O(mlog2m)$O(mlo{g}_{2}m)$

log2m<=log2n2=2log2n" role="presentation">log2m<=log2n2=2log2n$lo{g}_{2}m<=lo{g}_2{n}^2=2lo{g}_{2}n$ 两者是一个级别的，可以不用手写堆

851 ⭐

稀疏图，用邻接表存；

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N];
bool st[N];
typedef pair<int, int> PII;

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

int dijkstra() {
    // 初始化
    priority_queue, greater> heap;
    memset(dist, 0x3f, sizeof dist);
    heap.push({0, 1});
    dist[1] = 0;
    while (heap.size()) {
        // 查找t O(logn)
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        // 更新堆 O(m)
        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({w[i] + t.first, j});
            }
        }
    }
    return dist[n] != 0x3f3f3f3f ? dist[n] : -1;
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    return 0;
}

Bellman-Ford

结构体存 a,b,w 然后开个数组；执行后满足任意边 dist[b] <= dist[a] + w （三角不等式）

• for n次
  • for 所有边 a,b,w
    • dist[b] = min(dist[b],back[a]+w) （松弛操作）
• back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点

1到n的路径上有负权回路的话，最短路不存在（而spfa要求图中不能有任何负环）

迭代k次相当于从原点经过不超过k条边走到每个点的最短距离；该算法可以用于判断负环

853

853. 有边数限制的最短路 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

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

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        // IMPORTANT 避免串联
        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);
        }
    }
    // IMPORTANT 避免 5-(-2)->n 的情况
    if (dist[n] > 0x3f3f3f3f / 2)
        return 0x3f3f3f3f;
    else
        return dist[n];
}

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

    int t = bellman_ford();
    if (t == 0x3f3f3f3f)
        puts("impossible");
    else
        cout << t;
    return 0;
}

SPFA

必须图里没有负环，99%的最短路问题没有负环。用宽搜优化贝尔曼-福特算法

• 队列里存所有需要变小的节点，然后宽搜

851 ⭐

851. spfa求最短路 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N];
bool st[N];
typedef pair<int, int> PII;

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

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    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 0x3f3f3f3f;
    else
        return dist[n];
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f)
        puts("impossible");
    else
        cout << t;
    return 0;
}

852 ⭐

AcWing 852. spfa判断负环 - AcWing

cnt 数组维护原点到各点的边数，如果 cnt[x] >= n 则有负环；注意一开始需要把所有点放入

highlighter- arduino

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N], cnt[N];
bool st[N];
typedef pair<int, int> PII;

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;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }

    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;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (spfa())
        puts("Yes");
    else
        puts("No");
    return 0;
}

Floyed

• 邻接矩阵 d
• for k=1 k<=n k++
  • for i=1 i<=n i++
    • for j=1 j<=n j++
      • d(i,j) = min(d(i,j),d(i,k)+d(k,j))

基于DP，k,i,j 从 i 点出发只经过 1~k 中间点到达 j 的最短距离

854

854. Floyd求最短路 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 

using namespace std;

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

void floyed() {
    for (int k = 1; k <= n; k++)
        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= n; i++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    cin.tie(0);
    cin >> 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] = 0x3f3f3f3f;

    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }
    floyed();
    while (Q--) {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > 0x3f3f3f3f / 2)
            puts("impossible");
        else
            cout << d[a][b] << endl;
    }

    return 0;
}

最小生成树

最小生成树问题99%对应的图都是无向图，正边和负边都可以

• 普利姆算法 Prim
  • 朴素版Prim O(n2)" role="presentation">O(n2)$O(n^2)$ 稠密图
  • 堆优化Prim O(mlog2n)" role="presentation">O(mlog2n)$O(mlo{g}_{2}n)$ 稀疏图，不常用
• 克鲁斯卡尔算法 Kruskal O(mlog2m)" role="presentation">O(mlog2m)$O(mlo{g}_{2}m)$ 稀疏图，常用

Prim

与Dijkstra非常类似，不同的是用 t 更新其他点到集合s的距离，而不是其他点到原点的距离。集合s是当前已经在集合中的点；不在集合内的点，每个点连向集合的边的最短距离，无边为INF

最小生成树的边就是选中 t 时，t 与 集合s之间的边。

858

858. Prim算法求最小生成树 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

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[j] < dist[t])) t = j;
        if (i && dist[t] == INF) return INF;
        if (i)
            res +=
                dist[t];  // ^ 在更新 dist 之前累加，因为有自环问题（-10权重）
        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return res;
}

int main() {
    cin.tie(0);
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

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

    int t = prim();
    if (t == INF)
        puts("impossible");
    else
        cout << t;

    return 0;
}

Kruskal

不需要用邻接表或邻接矩阵存图，只要存每条边（结构体数组）

• 将所有边ab按w重小到大排序（快排）O(mlog2m)" role="presentation">O(mlog2m)$O(mlo{g}_{2}m)$
• 枚举每条边ab w （相当于并查集简单应用 O(m)" role="presentation">O(m)$O(m)$）
  • 如果ab不连通，将ab加到集合里面来

859 ⭐

AcWing 859. Kruskal算法求最小生成树 - AcWing

highlighter- arduino

#include 
#include 
#include 

using namespace std;

const int N = 2e5 + 10;
int n, m;
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 main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges + m);
    // ^ 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;

    int res = 0, cnt = 0;
    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)
        puts("impossible");
    else
        cout << res;
    return 0;
}

二分图

• 判断是否二分图：DFS 染色法 O(n+m)" role="presentation">O(n+m)$O(n+m)$
• 求二分图最大匹配：匈牙利算法 最坏O(nm)" role="presentation">O(nm)$O(nm)$，实际运行时间远小于O(nm)" role="presentation">O(nm)$O(nm)$

染色法

二分图：把所有点划分成两个集合，集合内没有边，集合之间有边；当且仅当图中不含奇数环（环中边的数量是奇数）

可以用 DFS、BFS 模拟染色过程，出现矛盾就不是二分图

860

AcWing 860. 染色法判定二分图 - AcWing

highlighter- cpp

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

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

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;
        } else if (color[j] == c)
            return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    if (flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

匈牙利

返回二分图最大匹配（最多的边数，没有两条边共用一个点）

861

861. 二分图的最大匹配 - AcWing题库

highlighter- arduino

#include 
#include 
#include 
#include 

using namespace std;

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

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

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

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 main() {
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    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;
    return 0;
}

372 ⭐⭐

372. 棋盘覆盖 - AcWing题库

每个卡片塞2个格子，把格子看成点，把卡片看成边，则只要能放卡片的相邻两个格子就连一条边。考虑卡片不会重叠，一定是一个二分图。

二分图最大匹配：匈牙利算法 (男女配对算法 我有多的选择就让给你 你有多的选择就让给我)

highlighter- arduino

#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// dfs 
bool find(int x, int y)
{
    for (int i = 0; i < 4; i ++ )//枚举邻点
    {
        int a = x + dx[i], b = y + dy[i];
        if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b])//不是坏点 没遍历过
        {
            // 则男[x,y] 和 女[a,b]能够配对 
            st[a][b] = true;
            PII t = match[a][b];// 
            //1 t.x==-1说明女[a,b]还没和其他人配对 则男[x,y]和女[a,b]可以直接配对
            //2 女[a,b]已经有人配对,但和女[a,b]配对的男t还有其他选项
            //  男t放弃和女[a,b]配对 让女[a,b]给男[x,y]配对(我感动了)
            if (t.x == -1 || find(t.x, t.y))
            {
                match[a][b] = {x, y};
                return true;
            }
        }
    }

    return false;
}

int main()
{
    cin >> n >> m;
    while(m--)
    {
        int x,y;
        cin >> x >> y;
        g[x][y] = true;
    }
    memset(match,-1,sizeof match);
    int res = 0;
    // 枚举所有和为奇数的点
    for(int i=1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            if((i+j)%2 && !g[i][j])
            {
                memset(st,0,sizeof st);//每次都需要清空st数组，因为匹配好的一对可能会有下家
                if(find(i,j))res++;//如果[i,j]能配对
            }
        }
    }
    cout << res << endl;
    return 0;
}

• DFS
•     842
•     843
•         搜索顺序、1
•         搜索顺序、2
• BFS
•     844
•     845 ⭐ Airbnb面试
• 树与图
•     邻接矩阵
•     邻接表 ⭐
• DFS 树与图
•     846 ⭐⭐
• BFS 树与图
•     847 ⭐
• 有向图的拓扑序列
•     848 ⭐
• 最短路
• 朴素Dijkstra
•     849
• 堆优化Dijkstra
•     851 ⭐
• Bellman-Ford
•     853
• SPFA
•     851 ⭐
•     852 ⭐
• Floyed
•     854
• 最小生成树
• Prim
•     858
• Kruskal
•     859 ⭐
• 二分图
• 染色法
•     860
• 匈牙利
•     861
•     372 ⭐⭐

__EOF__