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

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

转载作者：我是一只小鸟更新时间：2023-09-05 14:31:13

常用代码模板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

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

初始化所有点到起点距离：dis[1] = 0，dis[i] = +∞ 。
集合s：存储已经确定最短距离的点。
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;
}

最后此篇关于C++算法之旅、06基础篇|第三章图论的文章就讲到这里了,如果你想了解更多关于C++算法之旅、06基础篇|第三章图论的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：会员权益-需求调查：需要什么样的云服务器优惠

文章推荐： WPF学习-自定义窗体（二）

文章推荐：文盘Rust--生命周期问题引发的statichashmap锁

文章推荐： elasticsearchwildcard慢查询原因分析(深入到源码!!!)

vue3快速入门系列——基础
vue3 快速入门系列 - 基础前面我们已经用 vue2 和 react 做过开发了。从 vue2 升级到 vue3 成本较大，特别是较大的项目。所以许多公司对旧项目继续使用vue2，新项目则
C# 基础
C# 基础 C#项目创建这里注意win10虚拟机需要更新下补丁，不然直接下载visual studio 2022会显示版本不支持 HelloWorld C#的类文件都是以.cs结尾，入口方法为sta
iPhone内存管理(基础)
关于 iPhone 内存管理的非常基本的问题: 假设我有一个 viewController，其中有几个 subview 也由 viewController 控制。当我删除顶部 viewControll
C指针处理(基础)
我仍在努力适应指针。不是概念——我理解内存位置、匹配可变长度的指针增量等——这是语法。这是一个我认为是我感到困惑/无法直观把握的原因之一: int a = 42; 在一个int大小的内存空间中分配并放
Kafka-基础
1. 简介 Kafka（Apache Kafka）是一种分布式流数据平台，最初由LinkedIn开发，并于后来捐赠给Apache软件基金会，成为了一个Apache顶级项目。它被设计用于处理大规
学习mysql之后的一点总结(基础)
1.想要在命令提示符下操作mysql服务器，添加系统变量。（计算机-系统属性——环境变量——path） 2.查询数据表中的数据； select selection_lis
MySQL数据库 ---MySQL表的增删改查(基础)
MySQL表的增删改查(基础) 1. CRUD 注释：在SQL中可以使用“–空格+描述”来表示注释说明 CRUD 即增加(Create)、查询(Retrieve)、更新(Update)、删除(Dele
javascript - 基础 - 在关闭另一个模式时打开一个模式
我有一个网页，可以在加载时打开显示模式，在这个模式中，我有一个可以打开第二个模式的链接。当第二个模式关闭时(通过单击关闭按钮或单击模式外部)，我想重新打开第一个模式。对于关闭按钮，我可以通过向具有
ios - 核心数据提取属性 - 基础
使用 Core Data Fetched Properties，我如何执行这个简单的请求: 我希望获取的属性 ( myFetchProp ) 存储 StoreA ，它应该这样做: [myFetchPr
ios - 核心基础vs基础或核心基础+基础
关闭。这个问题是opinion-based .它目前不接受答案。想改进这个问题？更新问题，以便 editing this post 可以用事实和引用来回答它. 8年前关闭。 Improve this
drupal - 开发Drupal网站的前端-基础
最近，我得到了一个现有的Drupal项目，并被要求改进前端(HTML，JavaScript，CSS)。我在Django，PHP，Ruby等方面具有大量的前端和后端开发经验，但是我没有任何Drupal经
Java 扫描器类 - 基础
我试图让我的用户通过使用扫描仪类来决定要做什么，但我有一个问题，代码一旦运行就不会激活，并且它不会让我跳过任何行。我的代码如下所示: Scanner input = new Scanner(S
Java [基础] 对象问题
对模糊的标题表示歉意，因为我想不出这个名字是什么。基本上创建一个计算学生财务付款的小程序。当我运行它时，它计算对象限额没有问题。然而，无论我尝试什么，对象“助学金”似乎除了 0 之外什么也没有提出。
C 基础 - 被调用的对象不是函数或函数指针
这是我的代码 - main() { double x; double y = pow(((1/3 + sin(x/2))(pow(x, 3) + 3)), 1/3); prin
javascript - 基础 - 变量引用
如果我的术语在这个问题上有误，我们深表歉意。采取以下功能: i = 1; v = i * 2; for (j = 0; j < 4; j++ ) { console.log(v);
Android 基础 - 不同的类文件
我的应用程序中有不同的类文件。我有 5 个类，其中 2 个是 Activity ，1 个是运行的服务。其他 2 个只是类。这两个类中变量的生命周期是多少。我知道一个 Activity 可以被操作系统杀
Java 基础 - 实现在哪里进行？
例如，一个方法返回一个 List 类型的对象。 public List bojangles () ... 一些代码调用方法FooBar.bojangles.iterator(); 我是 Java 的新
css - 网格问题 - 基础
我遇到了一个奇怪的问题，网格的大小不适合我的屏幕。当我使用 12 列大时，它只占据屏幕的 1/3 的中间，请参见图像。我不确定是什么导致了这个问题。我没有任何会导致这种情况发生的奇怪 CSS。我不会在
C++ 头文件(基础)
我尝试使用头文件和源文件，但遇到了问题。因此，我对我正在尝试做的事情做了一个简化版本，我在 CodeBlocks 中遇到了同样的错误(undefined reference to add(double
css - (基础)带有背景图像的网格单元格突破
我正在为我的网格系统使用基础，但这在任何网格系统中都可能是一个问题。我基本上用一个容器包裹了 3 个单元格，但其中一个单元格应该长到页面边框(留在我的 Sampe-Image 中)但这也可能在右侧)。

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城