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

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

DFS

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

  • 数据结构:stack
  • 空间:需要记住路径上的点,\(O(h)\)
  • ⭐ BFS使用空间少;无最短路性质

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

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


842

842. 排列数字 - AcWing题库

#include <algorithm>
#include <cstdio>
#include <iostream>

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行放满,类似全排列

#include <algorithm>
#include <cstdio>
#include <iostream>

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

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

#include <algorithm>
#include <cstdio>
#include <iostream>

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(2^h)\)
  • ⭐ BFS使用空间多;有最短路性质(前提图所有边权重都为 1)

844

844. 走迷宫 - AcWing题库

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

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

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<string,int>
  • 状态转移
    • 想象成3*3的位置;然后把x移动到4个位置上去判断,再恢复成字符串;难点是二维位置与一维位置间的转换
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start) {
    string end = "12345678x";
    queue<string> q;
    unordered_map<string, int> 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(n^2)\)适合存储稠密图

邻接表 ⭐

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


DFS 树与图

\(O(n+m)\)

846 ⭐⭐

AcWing 846. 树的重心 - AcWing

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

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)\)

847 ⭐

AcWing 847. 图中点的层次 - AcWing

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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题库

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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(n^2)\) 适用于稠密图
      • 堆优化版Dijkstra:\(O(mlog_2n)\) 适用于稀疏图
    • 存在负权边
      • 贝尔曼-福特 Bellman-Ford:\(O(nm)\)
      • 优化贝尔曼-福特 SPFA:一般\(O(m)\),最坏\(O(nm)\)
  • 多源汇最短路:起点与终点不确定(一对起点终点)
    • 弗洛伊德 Floyd:\(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题库

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

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

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 中距离原点最近的点共执行 \(n^2\) 次;更新dis数组相当于遍历了所有边,共执行 m 次;**可以对这两个操作进行堆优化,前者变\(O(1)*O(n)=O(n)\),后者变\(O(log_2n)*O(m)=O(mlog_2n)\) **

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

前者有n个元素,后者可能m个元素;使用优先队列时间复杂度可能变成\(O(mlog_2m)\)

\(log_2m <= log_2n^2 = 2log_2n\) 两者是一个级别的,可以不用手写堆


851 ⭐

稀疏图,用邻接表存;

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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<PII, vector<PII>, greater<PII>> 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题库

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

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题库

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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 则有负环;注意一开始需要把所有点放入

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

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题库

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

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(n^2)\) 稠密图
    • 堆优化Prim \(O(mlog_2n)\) 稀疏图,不常用
  • 克鲁斯卡尔算法 Kruskal \(O(mlog_2m)\) 稀疏图,常用

Prim

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

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

858

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

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

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(mlog_2m)\)
  • 枚举每条边ab w (相当于并查集简单应用 \(O(m)\)
    • 如果ab不连通,将ab加到集合里面来

859 ⭐

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

#include <algorithm>
#include <cstdio>
#include <iostream>

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)\)
  • 求二分图最大匹配:匈牙利算法 最坏\(O(nm)\),实际运行时间远小于\(O(nm)\)

染色法

二分图:把所有点划分成两个集合,集合内没有边,集合之间有边;当且仅当图中不含奇数环(环中边的数量是奇数)

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

860

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

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

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题库

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

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个格子,把格子看成点,把卡片看成边,则只要能放卡片的相邻两个格子就连一条边。考虑卡片不会重叠,一定是一个二分图。

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

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

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

热门相关:我有一座恐怖屋   今天也没变成玩偶呢   隐婚试爱:娇妻,好甜!   隐婚试爱:娇妻,好甜!   重生之女将星