C++演演算法之旅、06 基礎篇 | 第三章圖論

DFS

儘可能往深處搜，遇到葉子節點（無路可走）回溯，恢復現場繼續走

資料結構：stack
空間：需要記住路徑上的點，\(O(h)\)。
⭐ BFS使用空間少；無最短路性質

每個DFS一定對應一個搜尋樹；要考慮用什麼順序遍歷所有方案；DFS就是遞迴

剪枝：提前判斷當前方案不合法，就不用繼續往下走了，直接回溯

842

#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 基礎篇 | 第三章 圖論

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 ⭐⭐

C++演演算法之旅、06 基礎篇 | 第三章圖論