图论
发表算法13 分钟读完 (大约2024个字)

图论

图论算法一般都是揉在一起的，很难单独把算法拆开讲，所以直接上题目吧。分类是大致分的，其实有很多是交叉的。

二叉树

二叉树的遍历有三种，分别为前序遍历，中序遍历和后序遍历，并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

前序遍历：按 根 左 右 的顺序进行；

中序遍历：按 左 根 右 的顺序进行；

后序遍历：按 左 右 根 的顺序进行。

最短路 & 生成树

算法复杂度

  • 多源最短路Floyd：严格 $O(n^3)$
  • 单源最短路Dijkstra：
    • 朴素：严格 $O(n^2)$
    • 优先队列优化：均摊 $O((e+n) \log n)$
  • Bellman-Ford：
    • 最多松弛 $n-1$ 次
    • 严格 $O(ne)$
  • SPFA：
    • 即队列优化Bellman-Ford
    • 最坏 $O(ne)$，最好 $O(1)$

板子

咕咕咕

如何卡掉 SPFA

见 https://www.zhihu.com/question/292283275/answer/484871888

P1967 货车运输

最大生成树，然后跑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
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4+10, M = 1e5+10, INF = 0x3f3f3f3f;

struct node {
    int id, u, v, w, next;
} e[M], e1[M];
int h[N], tot = 0, tot1 = 0, n, m;

int fa[N][15], dep[N], dis[N][15];
int vis[N];
bool edg[M];

void add(int u, int v, int w) {
    e1[tot1] = e[tot] = {tot, u, v, w, h[u]}; h[u] = tot++; tot1++;
    e[tot] = {tot, v, u, w, h[v]}; h[v] = tot++;
}

int bc[N];
int root(int u) {
    return bc[u] == u ? u : bc[u] = root(bc[u]);
}

bool cmp(node a, node b) {
    return a.w > b.w;
}
void dfs(int u, int f, int vi) {
    vis[u] = vi;
    for(int i = h[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if(v == f) continue;
        if(edg[i] or edg[i^1]) {
            dep[v] = dep[u] + 1;
            fa[v][0] = u;
            dis[v][0] = e[i].w;
            dfs(v, u, vi);
        }
    }
}

void lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    int ans = INF;
    int t = dep[x] - dep[y];
    for(int i=14; i>=0; --i) {
        if(t >= (1<<i)) {
            ans = min(ans, dis[x][i]);
            x = fa[x][i];
            t -= (1<<i);
        }
    }
    if(x == y) {
        printf("%d\n", ans);
        return;
    }
    for(int i=14; i>=0; --i) {
        if(fa[x][i] != fa[y][i]) {
            ans = min(ans, dis[x][i]);
            ans = min(ans, dis[y][i]);
            x = fa[x][i]; y = fa[y][i];
        }
    }
    //printf("lca:%d\n", fa[x][0]);
    printf("%d\n", min(ans, min(dis[x][0], dis[y][0])));
}
int main() {
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i=1; i<=m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    
    sort(e1, e1+tot1, cmp);
    for(int i=1; i<=n; ++i) bc[i] = i;
    for(int i=0; i<tot1; ++i) {
        int u = e1[i].u, v = e1[i].v;
        int u1 = root(u), v1 = root(v);
        if(u1 != v1) {
            edg[e1[i].id] = true;
            bc[v1] = u1;
        }
    }
    
    for(int i=1; i<=n; ++i) {
        if(bc[i] == i) {
            dfs(i, 0, i);
            for(int j=0; j<=14; ++j) {
                fa[i][j] = i;
                dis[i][j] = INF;
            }
        }
    }
    
    for(int i=1; i<=14; ++i) {
        for(int j=1; j<=n; ++j) {
            fa[j][i] = fa[fa[j][i-1]][i-1];
            dis[j][i] = min(dis[j][i-1], dis[fa[j][i-1]][i-1]);
        }
    }
    
    int query; scanf("%d", &query);
    for(int i=1; i<=query; ++i) { 
        int x, y; scanf("%d%d", &x, &y);
        if(vis[x] != vis[y]) { printf("-1\n"); continue; }
        lca(x, y);
    }
    
    return 0;
}

P1073 最优贸易

分层图，最短路

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
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <queue>
#include <map>
using namespace std;

const int N = 330000, M = 1650000;
struct node {
    int u, v, w, next;
    node() {}
    node(int _u, int _v, int _w, int _next): u(_u), v(_v), w(_w), next(_next) {}
} e[M << 1];
int h[N], tot = 0;

inline void add(int u, int v, int w = 0) {
    e[tot] = node(u, v, w, h[u]);
    h[u] = tot++;
}

int n, m, w[N]; bool vis[N]; int dis[N];
int main() {
    
    #ifdef DEBUG
    freopen("p1073_1.in", "r", stdin);
    #endif

    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &w[i]);
    }
    memset(h, -1, sizeof h);
    for(int i=1, x, y, z; i<=m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        if(z == 1) add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
        else {
            add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
            swap(x, y);
            add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
        }
    }
    
    for(int i=1; i<=n; ++i) {
        add(i+n, i, w[i]);
        add(i, i+2*n, -w[i]);
    }
    
    queue<int> q;
    
    memset(dis, 0x3f, sizeof dis);
    q.push(n+1); vis[n+1] = true; dis[n+1] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop(); vis[u] = false;
        for(int i=h[u]; i!=-1; i=e[i].next) {
            int v=e[i].v;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        } 
    }
    
    printf("%d\n", -dis[n*3]);
    
    return 0;
}

P1119 灾后重建

很重要的题目，考察了 Floyd的本质。

Floyd

用 $dis[k][i][j]$ 表示 i 和 j 之间可以通过编号为 $1\dots k$ 的节点的最短路径，显然，$dis[0][i][j]$ 就是原始邻接矩阵数据。

状态转移方程：

$$
dis[k][i][j]=min(dis[k-1][i][j],dis[k-1][i][k]+dis[k-1][k][j])
$$

Floyd 的本质其实就是DP，只不过我们通常做题时利用了数据只会使用一次性的原理，把 dis 变成滚动数组，减少了一维，节省空间。

更多请见 https://www.cnblogs.com/fangwencai/p/4784914.html。

1
2
3
4
5
6
7
//提前将邻接矩阵存在 dis 数组里，其他不连通的地方初始化成无穷大
for(int k=1; k<=n; ++k) //枚举中间点
    for(int i=1; i<=n; ++i) //枚举起点
        if(i != k) //节省时间，如果一样就不往下走
            for(int j=1; j<=n; ++j) //枚举终点
                if(i != j and j != k) //继续判断，如果有一样的就不往下走
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); //状态转移方程，也就是所谓的松弛操作

只要我们能够利用 DP 特性，就能解决许多问题

再回来看这道题，文中说每个村子是不同时间修好的，而每个节点都按顺序给出，这不就是恰好相当于 Floyd的中间点吗？我们可以把 k轮 DP分开做，每输入一个点，就用这个点当中转站把最短距离更新一遍，也就是跑一遍 DP。

Code:

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 220;

int t[N];

struct query {
    int id, x, y, t;
} a[55000];

int res[55000], n, m, dp[N][N];
int main() {
    
    //freopen("P1119_2.in", "r", stdin); 
    
    scanf("%d%d", &n, &m);
    
    for(int i=1; i<=n; ++i) {
        scanf("%d", t+i);
    }
    t[n+1] = 0x3f3f3f3f;
    
    memset(dp, 0x3f, sizeof dp);
    
    for(int i=1; i<=n; ++i) dp[i][i] = 0;
    for(int i=1; i<=m; ++i) { int u, v, w;
        scanf("%d%d%d", &u, &v, &w); ++u, ++v;
        dp[u][v] = dp[v][u] = w;
    }
    int q;
    scanf("%d", &q);
    for(int i=1; i<=q; ++i) {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].t);
        a[i].id = i; ++a[i].x, ++a[i].y; 
    }
    
    int cnt = 1;
    for(; a[cnt].t < t[1]; ++cnt) {
        res[a[cnt].id] = -1; 
    }
    
    for(int T=1; T<=n; ++T) {
        
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                dp[i][j] = min(dp[i][j], dp[i][T] + dp[T][j]);
            }
        }
            
        while(1) {
            if(cnt > q) break;
            if(a[cnt].t >= t[T] and a[cnt].t < t[T+1]); else break;
            if(a[cnt].x > T or a[cnt].y > T or dp[a[cnt].x][a[cnt].y] == 0x3f3f3f3f) {
                res[a[cnt].id] = -1;
            } else {
                res[a[cnt].id] = dp[a[cnt].x][a[cnt].y];
            }
            ++cnt;
        }
    }
    
    for(int i=1; i<=q; ++i) printf("%d\n", res[i]);
    return 0;
}

判负环

转自 @SingerCoder，%lgh

注意一定要判入队次数而不是松弛次数。

hack原理很简单：如果存在重边导致了多次松弛，那么对松弛次数的判断就会产生影响。解决方式就是判入队次数，虽然略慢，但是更稳。

Update[2020.7.26]：在写差分约束的时候想用spfa判无解，然后经过一系列的思考就有了下面这组新的hack数据：

1
2
3
4
5
6
7
8
9
10
11
input:
1
4 6
1 2 -3
1 3 -2
1 4 -1
2 3 -6
2 4 -5
3 4 -4
output:
NO

注意这组hack只对用链式前向星（而非vector）存边且判的是松弛次数（而非入队次数）的有效，而且该数据无重边无自环，比discuss里面的那个数据更有说服力。

首先hack原理就是对n号节点进行n-1轮松弛，每轮都有 $x( x \in [1,n-1])$ 次松弛，这样就能产生 $n^2$ 级别的松弛次数。

但是判入队次数就hack不掉了，每轮的第一次松弛会让n节点入队，但n节点只有在下一轮才会出队；因此本轮的其余所有松弛全部无法导致入队。

P3385 [模板]负环

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 2e3 + 10, M = 6e3 + 10;
struct node {
    int u, v, w, next;
} e[M];
int h[N], tot = 0;
int T, n, m;
inline void add(int u, int v, int w) {
    e[++tot] = {u, v, w, h[u]}; h[u] = tot;
} 

int dis[N], vis[N];
bool inq[N];

inline void spfa() {
    
    queue<int> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(inq, false, sizeof inq);
    
    dis[1] = 0; q.push(1); inq[1] = true; ++vis[1];
    while(!q.empty()) {
        
        int u = q.front(); q.pop(); inq[u] = false;//printf("%d\n", u);
        for(int i = h[u]; i ; i = e[i].next) {
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!inq[v]) {
                    inq[v] = true;
                    ++vis[v];
                    if(vis[v] > n-1) {
                        printf("YES\n");
                        return;
                    }
                    q.push(v);
                }
            }
        }
    }
    printf("NO\n");
}
int main() {
    
    //freopen("P3385_2.in", "r", stdin);
    
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(h, 0, sizeof h); tot = 0;
        for(int i=1; i<=m; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            if(w >= 0) {
                add(u, v, w);
                add(v, u, w);
            } else add(u, v, w);
            //printf("%d ", i);
        }
        spfa();
    }
    return 0;
}

基环树

n 个点 n 条边 只有一个环 枚举断边

P5022 [NOIp2018TG]旅行

图论

https://snow.js.org/graph-theory/

发布于

2020-07-31

更新于

2023-01-11

许可协议

#

评论

分类

最新文章

标签

AI3
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Gulp1
Hexo4
LCA1
PB_DS1
PWA1
SSH1
STL2
Vercel1
二分图2
动态规划3
匹配2
单调队列2
博客4
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
应用程序1
排序2
数学2
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法26
网络流5
记忆化搜索4
部署3
随感1
随笔1
×