Skip to content

Latest commit

 

History

History
508 lines (409 loc) · 10 KB

算法题目.md

File metadata and controls

508 lines (409 loc) · 10 KB
Raw

搜索与图论

  1. DFS
    1. 全排列
    2. N皇后 II
  2. BFS
    1. 广搜过程表
    2. 八数码
  3. 树与图的遍历
  4. 拓扑排序
    1. 课程表 II
  5. 最短路
    1. Dijkstra求最短路 I
    2. spfa求最短路
  6. 最小生成树
    1. 【模板】最小生成树
  7. 二分图：染色法、匈牙利算法
    1. 【模板】二分图最大匹配

题解

全排列

class Solution {
public:

    bool vis[100];
    vector<vector<int>> ans;

    vector<int> nums;

    void dfs(vector<int> & vec) {
            if (vec.size() == nums.size()) {
                ans.push_back(vec);
                return;
            }
            for (int i = 0; i < nums.size(); i++) {
                if (!vis[i]) {
                    vis[i] = true;
                    vec.push_back(nums[i]);
                    dfs(vec);
                    vec.pop_back();
                    vis[i] = false;
                }
            }
        }

    vector<vector<int>> permute(vector<int>& nums) {
        this->nums = nums;
        vector<int> tmp;
        dfs(tmp);
        return ans;
    }
};

N皇后（普通版）

class Solution {
public:
    int res = 0;
    int a[100000 + 10];
    bool vis[100000 + 10];
    int n;

    void dfs(int dep) {
        if (dep == n) {
            res++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (vis[i] == false) {
                bool ok = true;
                for (int j = 0; j < dep; j++)
                    if (abs(i - a[j]) == (dep - j)) {
                        ok = false;
                        break;
                    }
                if (ok) {
                    vis[i] = true;
                    a[dep] = i;
                    dfs(dep + 1);
                    vis[i] = false;
                }
            }
        }
    }

    int totalNQueens(int n) {
        this->n = n;
        dfs(0);
        return res;
    }
};

N皇后（对角线优化）

class Solution {
public:
    int ans;
    int n;
    vector<bool> cols, d, rd;
    int totalNQueens(int _n) {
        n = _n;
        cols = vector<bool>(n);
        d = rd = vector<bool>(2 * n);
        dfs(0);
        return ans;
    }

    void dfs(int u) {
        if (u == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!cols[i] && !d[u + i] && !rd[u - i + n]) {
                cols[i] = d[u + i] = rd[u - i + n] = true;
                dfs(u + 1);
                cols[i] = d[u + i] = rd[u - i + n] = false;
            }
        }
    }
};

广搜过程表

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 20 + 10;

int mm[N][N];
int n, m;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void bfs(int si, int sj) {
    mm[si][sj] = 0;
    queue<pair<int, int>> q;
    q.push({ si, sj });
    while (q.size()) {
        auto cur = q.front(); q.pop();
        int x = cur.first;
        int y = cur.second;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && mm[nx][ny] == -1) {
                mm[nx][ny] = mm[x][y] + 1;
                q.push({ nx, ny });
            }
        }
    }
}


int main() {
    while (cin >> n >> m) {
        memset(mm, -1, sizeof mm);


        int si, sj;
        cin >> si >> sj;
        bfs(si - 1, sj - 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                cout << mm[i][j];
            cout << endl;
        }
    }
}

八数码

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;

unordered_map<string, int> vis;

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

int bfs(const string & start) {
    queue<string> q;
    q.push(start);
    vis[start] = 0;
    while (q.size()) {
        string u = q.front(); 
        q.pop();
        int t = vis[u];
        if (u == "12345678x") {
            return t;
        }
        int k = u.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) {
                string v = u;
                swap(v[xx * 3 + yy], v[x * 3 + y]);
                if (!vis.count(v)) q.push(v), vis[v] = t + 1;
            }
        }
    }
    return -1;
}

int main() {
    char ch;
    string str;
    while (cin >> ch) {
        str.push_back(ch);
    }
    cout << bfs(str) << endl;
}

课程表 II

class Solution {
public:

    static const int N = 1e5 + 10;
    int h[N], e[N], ne[N], idx;
    int in_degree[N];

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

    vector<int> findOrder(int n, vector<vector<int>>& g) {
        memset(h, -1, sizeof h);
        for (auto & vec : g)
            add(vec[1], vec[0]);

        int cnt = 0;
        vector<int> res;
        queue<int> q;
        for (int i = 0; i < n; i++) if (in_degree[i] == 0) q.push(i);

        while (q.size()) {
            int cur = q.front(); q.pop();
            cnt++;
            res.push_back(cur);
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int to = e[i];
                in_degree[to]--;
                if (in_degree[to] == 0) q.push(to);
            }
        }

        if (cnt == n) return res;
        return vector<int>();
    }
};

Dijkstra求最短路 I

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 500 + 10;
int g[N][N];
int dist[N];
bool st[N];
int n;

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i++) {
        int t = - 1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
            
        st[t] = true;
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main() {
    int m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
    }
            
    cout << dijkstra() << endl;
}

spfa求最短路

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

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

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

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

int dist[N];
bool st[N];

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    st[1] = true;
    while (q.size()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            int _w = w[i];
            if (dist[u] + _w >= dist[v]) continue;
            dist[v] = dist[u] + _w;
            if (!st[v]) q.push(v), st[v] = true;
        }
    }
    return dist[n] >= INF / 2 ? -1 : dist[n];
}

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

【模板】最小生成树

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 2e5 + 10;

struct Edge {
    int u, v, w;
} e[N];

int p[N];
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

void combine(int x, int y) {
    p[find(x)] = find(y);
}

int n, m;
int kru() {
    sort(e, e + m, [](auto a, auto b) {return a.w < b.w;});
    for (int i = 1; i <= n; i++) p[i] = i;
    int cnt = 1;
    int res = 0;
    for (int i = 0; i < m && cnt < n; i++) {
        auto edge = e[i];
        if (find(edge.u) != find(edge.v)) {
            combine(edge.u, edge.v);
            res += edge.w;
            cnt++;
        }
    }
    if (cnt == n) return res;
    return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    int t = kru();
    if (t == -1) cout << "orz";
    else cout << t;
}

【模板】二分图最大匹配

#include <iostream>
#include <cstring>
using namespace std;

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

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

int f[N];
bool st[N];

bool dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (st[v]) continue;
        st[v] = true;
        if (!f[v] || dfs(f[v])) {
            f[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    memset(h, -1, sizeof h);

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

    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(st, false, sizeof st);
        if (dfs(i)) res++;
    }
    
    cout << res << endl;
}