Sunglassman 的算法竞赛板子整理——图论篇

发表于 更新于 分类于 ， ，

Sunglassman 的算法竞赛板子整理——图论篇

欧拉路径

P7771 【模板】欧拉路径

题目描述

求有向图字典序最小的欧拉路径。

输入格式

第一行两个整数 $n,m$ 表示有向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
4 6
1 3
2 1
4 2
3 3
1 2
3 4

输出 #1

1
1 2 1 3 3 4 2

输入输出样例 #2

输入 #2

1
2
3
4
5
6
5 5
1 2
3 5
4 3
3 4
2 3

输出 #2

1
1 2 3 4 3 5

输入输出样例 #3

输入 #3

1
2
3
4
4 3
1 2
1 3
1 4

输出 #3

1
No

说明/提示

对于 $50%$ 的数据，$n,m\leq 10^3$。

对于 $100%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$m\leq 2\times 10^5$。

保证将有向边视为无向边后图连通。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

constexpr int M = 2e5 + 10;

multiset<int> adj[M]; // 千万注意不要用set，要用multiset
bool vis[M];
vector<int> res;
int deg[M], indeg[M];

void dfs(int x) {
    while (!adj[x].empty()) {
        int t = *adj[x].begin();
        adj[x].erase(adj[x].begin());
        dfs(t);
    }
    res.push_back(x);
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        adj[x].insert(y);
        deg[x]++, indeg[y]++;
    }
    int beg = -1, des = -1;
    for (int i = 1; i <= n; ++i) {
        if (abs(deg[i] - indeg[i]) > 1) {
            cout << "No\n";
            return 0;
        }
        if (deg[i] == indeg[i] + 1) {
            if (beg == -1) beg = i;
            else {
                cout << "No\n";
                return 0;
            }
        }
        else if (deg[i] == indeg[i] - 1) {
            if (des == -1) des = i;
            else {
                cout << "No\n";
                return 0;
            }
        }
    }
    if (beg != -1) dfs(beg);
    else dfs(1);
    reverse(res.begin(), res.end());
    if (res.size() != m + 1) {
        cout << "No\n";
        return 0;
    }
    for (auto x : res) cout << x << ' ';
    cout << '\n';
    return 0;
}

Dijkstra

P4779 【模板】单源最短路径（标准版）

题目描述

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$。
第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

1
0 2 4 3

说明/提示

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Created by Sunglassman

struct Node {
    int id;
    ll w;
    Node(int _id, ll _w) : id(_id), w(_w) {};
    bool operator < (const Node &oth) const {
        return oth.w < w;
    }
};

void tasks() {
    int n, m, s; cin >> n >> m >> s;
    vector<vector<Node>> adj(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v; ll w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }
    vector<ll> dis(n + 1, INF);
    dis[s] = 0;
    priority_queue<Node> pq;
    pq.emplace(s, dis[s]);
    vector<bool> vis(n + 1, false);
    while (!pq.empty()) {
        auto sto = pq.top(); pq.pop();
        int t = sto.id, d = sto.w;
        if (vis[t]) continue;
        vis[t] = true;
        for (const auto& it : adj[t]) {
            int u = it.id;
            ll w = it.w;
            if (dis[u] > dis[t] + w) {
                dis[u] = dis[t] + w;
                pq.emplace(u, dis[u]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << dis[i] << ' ';
    cout << EL;
}

Kruskal求最小生成树

P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

1
7

说明/提示

数据规模：

对于 $20%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

#define M 5005

int ast[M] = {0};
int x, y, z, n, m;
vector<pair<int, pair<int, int>>> edges;

int find_ast(int i) {
    return (ast[i] == i) ? i : (ast[i] = find_ast(ast[i]));
}

void union_set(int x, int y) {
    int rx = find_ast(x);
    int ry = find_ast(y);
    if (rx != ry) {
        ast[ry] = ast[rx];
    }
}

int kruskal() {
    sort(edges.begin(), edges.end());
    int res = 0;
    int cnt = 0;
    for (auto &eg : edges) {
        int weight = eg.first;
        int u = eg.second.first;
        int v = eg.second.second;
        if (find_ast(u) != find_ast(v)) {
            union_set(u, v);
            res += weight;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    return res;
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        ast[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        if (x > y) swap(x, y);
        edges.push_back({z, {x, y}});
    }

    int ss = kruskal();

    if (ss >= 0) cout << ss;
    else cout << "orz";

    return 0;

}

斜二进制LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q, rt; cin >> n >> q >> rt; // 树以rt为根，O(n)预处理O(log n)单次询问
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y), adj[y].push_back(x);
    }
    vector<int> lb(n + 1), dep(n + 1), fa(n + 1);
    auto dfs = [&](auto&& self, int u)->void {
        int f = fa[u], lf = lb[f], llf = lb[lf];
        lb[u] = dep[f] - dep[lf] != dep[lf] - dep[llf] ? f : llf;
        dep[u] = dep[f] + 1;
        for (auto t : adj[u]) if (t != f) fa[t] = u, self(self, t);
    };
    auto lca = [&](int x, int y)->int {
        if (dep[x] < dep[y]) swap(x, y);
        while (dep[x] > dep[y]) {
            if (dep[lb[x]] < dep[y]) x = fa[x];
            else x = lb[x];
        }
        while (x != y) {
            if (lb[x] == lb[y]) x = fa[x], y = fa[y];
            else x = lb[x], y = lb[y];
        }
        return x;
    };
    dfs(dfs, rt);
    while (q--) {
        int x, y; cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
}

Kruskal 重构树 & 倍增LCA

P1967 [NOIP 2013 提高组] 货车运输

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x, y, z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x \neq y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出 #1

1
2
3
3
-1
3

说明/提示

对于 $30%$ 的数据，$1 \le n < 1000$，$1 \le m < 10,000$，$1\le q< 1000$；

对于 $60%$ 的数据，$1 \le n < 1000$，$1 \le m < 5\times 10^4$，$1 \le q< 1000$；

对于 $100%$ 的数据，$1 \le n < 10^4$，$1 \le m < 5\times 10^4$，$1 \le q< 3\times 10^4 $，$0 \le z \le 10^5$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

constexpr int M = 1e5 + 10;
constexpr int B = 14;

struct Node {
    int u, v, w;
    Node() = default;
    Node(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {};
    bool operator < (const Node& oth) const {
        return w > oth.w;
    }
} ed[M];

int pr[M], id;
std::vector<Node> adj[M];
int dep[M], fa[M][16], w[M];
int n, m;
std::vector<int> e[M];


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

void dfs(int x) {
    for (int k = 0; k < B; ++k) {
        fa[x][k + 1] = fa[fa[x][k]][k];
    }
    for (int y : e[x]) {
        fa[y][0] = x, dep[y] = dep[x] + 1, dfs(y);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int k = B; ~k; --k) {
        if (fa[x][k] && dep[fa[x][k]] >= dep[y]) {
            x = fa[x][k];
        }
    }
    if (x == y) return x;
    for (int k = B; ~k; --k) {
        if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
    }
    return fa[x][0];
}


int main() {
    std::cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        std::cin >> ed[i].u >> ed[i].v >> ed[i].w;
    }
    std::sort(ed, ed + m);
    for (int i = 1; i <= 2 * n; ++i) {
        pr[i] = i;
    }
    id = n;
    for (int i = 0; i < m; ++i) {
        int u = find(ed[i].u), v = find(ed[i].v);
        if (u == v) continue;
        pr[u] = pr[v] = ++id, e[id] = {u, v}, w[id] = ed[i].w; // 建立重构树
    }
    for (int i = 1; i <= id; ++i) {
        if (pr[i] == i) dfs(i);
    }
    int q, x, y; std::cin >> q;
    while (q--) {
        std::cin >> x >> y;
        std::cout << (find(x) == find(y) ? w[lca(x, y)] : -1) << '\n';
    }

    return 0;
}

Tarjan

TODO