基础搜索&图论算法

深搜, 广搜

DFS实现枚举排列数字
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int n, u;
set<int> st;
int curr[N];

void dfs() {
   
    if (u > n) {
   
        for (int i = 1; i <= n; ++i) cout << curr[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; ++i) {
   
        if (st.count(i)) continue;
        curr[u++] = i;
        st.insert(i);
        dfs();
        st.erase(i);
        u--;
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    u = 1;
    dfs();

    return 0;
}

DFS解决N皇后问题
解决精确覆盖问题最优解法是Dancing-Links, 这里直接暴力搜索出所有结果
在这里插入图片描述
因为同一行只能放置一个皇后, 因此可以按照行进行DFS, 到最后一行放置结束后必须已经放置了N个皇后, 辅助函数判断当前位置是否能放置皇后

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int n;
char curr[N][N];

bool is_valid(int x, int y) {
   
    for (int i = 1; i <= n; ++i) if (i != x && curr[i][y] == 'Q') return false;
    for (int i = 1; i <= n; ++i) if (i != y && curr[x][i] == 'Q') return false;

    for (int i = x - 1, j = y - 1; i >= 1 && j >= 1; i--, j--) if (curr[i][j] == 'Q') return false;
    for (int i = x - 1, j = y + 1; i >= 1 && j <= n; i--, j++) if (curr[i][j] == 'Q') return false;
    for (int i = x + 1, j = y + 1; i <= n && j <= n; i++, j++) if (curr[i][j] == 'Q') return false;
    for (int i = x + 1, j = y - 1; i <= n && j >= 1; i++, j--) if (curr[i][j] == 'Q') return false;
    return true;
}

void dfs(int u, int row) {
   
    if (row > n) {
   
        if (u == n) {
   
            for (int i = 1; i <= n; ++i) {
   
                for (int j = 1; j <= n; ++j) {
   
                    cout << curr[i][j];
                }
                cout << '\n';
            }
            cout << '\n';
        }
        return;
    }


    for (int j = 1; j <= n; ++j) {
   
        if (is_valid(row, j)) {
   
            curr[row][j] = 'Q';
            dfs(u + 1, row + 1);
            curr[row][j] = '.';
        }
    }
}

void init() {
   
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            curr[i][j] = '.';
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    init();

    dfs(0, 1);

    return 0;
}

广搜基础应用之走迷宫
双向循环队列实现广度优先搜索
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 110;
const int dx[4] = {
   0, -1, 0, 1}, dy[4] = {
   -1, 0, 1, 0};


int n, m;
int w[N][N], d[N][N];
bool st[N][N];

int bfs() {
   
    PII q[N * N];
    int h = 0, t = 0;

    q[t++] = {
   1, 1};
    st[1][1] = true;
    d[0][0] = 0;

    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == N * N) h = 0;

        for (int i = 0; i < 4; ++i) {
   
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || w[nx][ny] || st[nx][ny]) continue;

            d[nx][ny] = d[x][y] + 1;
            st[nx][ny] = true;

            if (nx == n && ny == n) return d[n][n];

            q[t++] = {
   nx, ny};
            if (t == N * N) t = 0;
        }
    }
    return d[n][m];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            cin >> w[i][j];
        }
    }

    cout << bfs() << '\n';

    return 0;
}

广搜基础应用之八数码问题
将矩阵转化为线性, 对于当前一维数组的坐标idx, 对应的矩阵中的坐标是[idx / 3, idx % 3], 假设在矩阵中的坐标是(x, y)转化为一位数组坐标就是x * 3 + y

为什么使用线性存储矩阵, 因为方便计算中间状态
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int dx[4] = {
   0, -1, 0, 1}, dy[4] = {
   -1, 0, 1, 0};
const int M = 1e5 + 10;
const string target = "12345678x";

string s;
map<string, int> mp;
set<string> st;

PII find(string &s) {
   
    int idx = 0;
    for (int i = 0; s[i]; ++i) {
   
        if (s[i] == 'x') {
   
            idx = i;
            break;
        }
    }
    return {
   idx / 3, idx % 3};
}

bool is_valid(string &s) {
   
    for (int i = 0; s[i]; ++i) {
   
        if (target[i] != s[i]) return false;
    }
    return true;
}

int bfs() {
   
    if (is_valid(s)) return 0;

    string q[M];
    int h = 0, t = 0;

    q[t++] = s;
    st.insert(s);

    while (h != t) {
   
        string str = q[h++];
        if (h == M) h = 0;

        auto [x, y] = find(str);
        for (int i = 0; i < 4; ++i) {
   
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;

            string n_str = str;
            swap(n_str[x * 3 + y], n_str[nx * 3 + ny]);
            if (st.count(n_str)) continue;

            mp[n_str] = mp[str] + 1;
            if (is_valid(n_str)) return mp[n_str];

            q[t++] = n_str;
            st.insert(n_str);
            if (t == M) t = 0;
        }
    }
    return -1;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    char c;
    for (int i = 0; i < 9; ++i) {
   
        cin >> c;
        s += c;
    }
    cout << bfs() << '\n';

    return 0;
}

树与图的存储及深度优先搜索和广度优先搜索

树的重心
需要注意的是计算所有子节点对当前节点的贡献
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

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

int n;
int head[N], ed[M], ne[M], idx;
int sz[N], res;


void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int fa) {
   
    sz[u] = 1;
    int max_son = 0;

    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        max_son = max(max_son, sz[v]);
    }

    int val = max(max_son, n - sz[u]);
    res = min(res, val);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    res = n;
    dfs(1, -1);

    cout << res << '\n';
    return 0;
}

图中点的层次
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = N;
const int INF = 0x3f3f3f3f;

int n, m;
int head[N], ed[M], ne[M], idx;

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

int bfs() {
   
    int d[N];
    memset(d, 0x3f, sizeof d);
    int q[N], h = 0, t = 0;

    d[1] = 0;
    q[t++] = 1;

    while (h != t) {
   
        int u = q[h++];
        if (h == N) h = 0;
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + 1 < d[v]) {
   
                d[v] = d[u] + 1;
                q[t++] = v;
                if (t == N) t = 0;
            }
        }
    }

    int res = d[n] == INF ? -1 : d[n];
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v;
        cin >> u >> v;
        add(u, v);
    }

    cout << bfs() << '\n';
    return 0;
}

有向图的拓扑排序

队列中的点都是入度为0的点
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int head[N], ed[M], ne[M], idx;
int in_deg[N];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void top_sort() {
   
    int res[N], cnt = 0;
    int q[N * 2], h = 0, t = 0;

    for (int i = 1; i <= n; ++i) {
   
        if (!in_deg[i]) q[t++] = i;
    }

    while (h != t) {
   
        int u = q[h++];
        if (h == N * 2) h = 0;
        res[cnt++] = u;
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            in_deg[v]--;
            if (!in_deg[v]) {
   
                q[t++] = v;
                if (t == N * 2) t = 0;
            }
        }
    }

    if (cnt != n) cout << -1 << '\n';
    else {
   
        for (int i = 0; i < n; ++i) cout << res[i] << ' ';
        cout << '\n';
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    memset(head, -1, sizeof head);

    for (int i = 0; i < m; ++i) {
   
        int u, v;
        cin >> u >> v;
        add(u, v);
        in_deg[v]++;
    }

    top_sort();
    return 0;
}

Dijkstra算法

算法时间复杂度 $O(Mlog⁡N)O(M\log N)$
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10, M = N;
const int INF = 0x3f3f3f3f;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

int dijkstra() {
   
    priority_queue<PII, vector<PII>, greater<>> q;
    int d[N];
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    q.push({
   0, 1});

    while (q.size()) {
   
        auto [dis, u] = q.top();
        q.pop();

        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] < d[v]) {
   
                d[v] = d[u] + w[i];
                q.push({
   d[v], v});
            }
        }
    }

    return d[n] == INF ? -1 : d[n];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    while (m--) {
   
        int u, v, val;
        cin >> u >> v >> val;
        add(u, v, val);
    }

    int res = dijkstra();
    cout << res << '\n';

    return 0;
}

Bellman-ford算法

适用于负权图以及边数限制的最短路, 算法时间复杂度 $O (MN)$
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, k;
struct Edge {
   
    int u, v, w;
} edges[M];

int bellman_ford() {
   
    int d[N];
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    int tmp[N];

    for (int i = 0; i < k; ++i) {
   
        memcpy(tmp, d, sizeof d);

        for (int j = 0; j < m; ++j) {
   
            auto [u, v, w] = edges[j];
            if (tmp[u] + w < d[v]) d[v] = tmp[u] + w;
        }
    }

    return d[n];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {
   u, v, w};
    }

    int res = bellman_ford();
    if (res > INF >> 1) cout << "impossible" << '\n';
    else cout << res << '\n';

    return 0;
}

Floyd算法

多源最短路适用于负权图, 适合求解所有点与点之间的最短路, 算法时间复杂度 $O(n ^ 3)$
在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, m, k;
int d[N][N];

void floyd() {
   
    for (int k = 1; k <= n; ++k) {
   
        for (int i = 1; i <= n; ++i) {
   
            for (int j = 1; j <= n; ++j) {
   
                if (d[i][k] != INF && d[k][j] != INF) {
   
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(d, 0x3f, sizeof d);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) d[i][i] = 0;
    
    for (int i = 0; i < m; ++i) {
   
        int u, v, val;
        cin >> u >> v >> val;
        d[u][v] = min(d[u][v], val);
    }

    floyd();

    while (k--) {
   
        int u, v;
        cin >> u >> v;
        int res = d[u][v];
        if (res == INF) cout << "impossible" << '\n';
        else cout << res << '\n';
    }

    return 0;
}

SPFA求最短路

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = N;
const int INF = 0x3f3f3f3f;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

int spfa() {
   
    int d[N];
    bool st[N];
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);
    int q[N], h = 0, t = 0;
    q[t++] = 1;
    d[1] = 0;
    st[1] = true;

    while (h != t) {
   
        int u = q[h++];
        if (h == N) h = 0;
        st[u] = false;

        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] != INF && d[u] + w[i] < d[v]) {
   
                d[v] = d[u] + w[i];
                if (st[v]) continue;
                q[t++] = v;
                st[v] = true;
                if (t == N) t = 0;
            }
        }
    }

    return d[n];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    while (m--) {
   
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }

    int res = spfa();
    if (res > INF >> 1) cout << "impossible" << '\n';
    else cout << res << '\n';
    return 0;
}

SPFA判负环

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

bool spfa() {
   
    int q[N], h = 0, t = 0;
    int cnt[N] = {
   0};
    bool st[N];
    int d[N];

    memset(st, false, sizeof st);
    memset(d, 0x3f, sizeof d);

    for (int i = 1; i <= n; ++i) {
   
        q[t++] = i;
        st[i] = true;
    }

    while (h != t) {
   
        int u = q[h++];
        if (h == N) h = 0;
        st[u] = false;

        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] < d[v]) {
   
                d[v] = d[u] + w[i];
                if (st[v]) continue;
                q[t++] = v;
                if (t == N) t = 0;
                st[v] = true;
                cnt[v]++;

                if (cnt[v] == n) {
   
                    return true;
                }
            }
        }
    }
    return false;
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, val;
        cin >> u >> v >> val;
        add(u, v, val);
    }

    cout << (spfa() ? "Yes" : "No") << '\n';
    return 0;
}

最小生成树

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

struct Edge {
   
    int u, v, w;

    bool operator<(const Edge &e) const {
   
        return w < e.w;
    }
} edges[M];

int n, m;
int p[N];

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

int kruskal() {
   
    sort(edges, edges + m);
    int res = 0;
    int cnt =  0;

    for (int i = 0; i < m; ++i) {
   
        auto [u, v, w] = edges[i];

        int fa1 = find(u), fa2 = find(v);
        if (fa1 == fa2) continue;
        res += w;
        p[fa2] = fa1;
        cnt++;
    }

    if (cnt != n - 1) return -INF;
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i <= n; ++i) p[i] = i;

    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {
   u, v, w};
    }

    int res = kruskal();

    if (res == -INF) cout << "impossible" << '\n';
    else cout << res << '\n';
    return 0;
}

染色法判断二分图

在这里插入图片描述
设定当前节点颜色是0代表未染色, 1代表黑色, 2代表白色, 对于二分图来说与当前节点连接的点的颜色一定是相反颜色的, 注意给定的是无向图

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int head[M], ed[M], ne[M], idx;
int color[N];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

bool dfs(int u, int val) {
   
    color[u] = val;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (!color[v]) {
   
            if (!dfs(v, 3 - val)) return false;
        }
        else if (color[v] == val) return false;
    }
    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    while (m--) {
   
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    for (int i = 1; i <= n; ++i) {
   
        if (!color[i]) {
   
            if (!dfs(i, 1)) {
   
                cout << "No" << '\n';
                return 0;
            }
        }
    }

    cout << "Yes" << '\n';
    return 0;
}

匈牙利算法求二分图最大匹配

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

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

int n1, n2, m;
int head[N], ed[M], ne[M], idx;
int match[N];
bool st[N];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

bool find(int u) {
   
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (!st[v]) {
   
            st[v] = true;
            // 当前V未匹配或者已经匹配但是能找到下家, 将当前V与U匹配
            if (!match[v] || find(match[v])) {
   
                match[v] = u;
                return true;
            }
        }
    }

    return false;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(head, -1, sizeof head);

    cin >> n1 >> n2 >> m;

    while (m--) {
   
        int u, v;
        cin >> u >> v;
        add(u, v);
    }

    int res = 0;
    for (int i = 1; i <= n1; ++i) {
   
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }

    cout << res << '\n';
    return 0;
}