图论

本文将介绍Dijkstra、Bellman-Ford、SPFA、Floyd等算法

注意：本文图文并茂

将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：L1@75666

1. `Dijkstra`算法

题目1

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];
int n, m;
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 1; i < n; i ++ ){
        int t = 0;
        for(int j = 1; j <= n; j ++ ){
            if(!st[j] && dist[t] > dist[j]) t = j;
        }
        for(int j = 1; j <= n; j ++ ){
            if(dist[j] > dist[t] + g[t][j]){
                dist[j] = dist[t] + g[t][j];
            }
        }
        st[t] = true;
    }
    if(dist[n] == INF) return -1;
    else return dist[n];
}
int main(){
    memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &m);
    int a, b, c;
    while(m -- ){
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    printf("%d\n", dijkstra());
    for(int i = 0; i <= n; i ++ ){
        printf("%s ", st[i] ? "true" : "false");
    }
    puts("");
    return 0;
}

题目2

Luogu P3371 【模板】单源最短路径（弱化版）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 5e5 + 10, INF = INT_MAX;
struct edge{
    int v, w;
};
int dist[N];
bool st[N];
vector<edge> e[N];
int n, m, s;
void dijkstra(int a){
    for(int i = 0; i <= n; i ++ ) dist[i] = INF;
    dist[a] = 0;
    for(int i = 1; i < n; i ++ ){
        int t = 0;
        for(int j = 1; j <= n; j ++ ){
            if(!st[j] && dist[t] > dist[j]) t = j;
        }
        st[t] = true;
        for(auto &edge: e[t]){
            int v = edge.v, w = edge.w;
            if(dist[v] > dist[t] + w) dist[v] = dist[t] + w;
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &s);
    int a, b, c;
    while(m -- ){
        scanf("%d%d%d", &a, &b, &c);
        e[a].push_back({b, c});
    }
    dijkstra(s);
    for(int i = 1; i <= n; i ++ ){
        printf("%d ", dist[i]);
    }
    return 0;
}

题目3

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

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10, INF = INT_MAX;
struct edge{
    int v, w;
};
int dist[N];
bool st[N];
int n, m, s;
vector<edge> e[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
void dijkstra(int s){
    for(int i = 0; i <= n; i ++ ) dist[i] = INF;
    dist[s] = 0;
    q.push({0, s}); // PII = {dist, edge} edge 到点 s 的距离dist
    while(q.size()){
        auto t = q.top();
        q.pop();
        int u = t.second;
        if(st[u]) continue;
        st[u] = true;
        for(auto &edge : e[u]){
            int v = edge.v, w = edge.w;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &s);
    int a, b, c;
    while(m -- ){
        scanf("%d%d%d", &a, &b, &c);
        e[a].push_back({b, c});
    }
    dijkstra(s);
    for(int i = 1; i <= n; i ++ ){
        printf("%d ", dist[i]);
    }
    return 0;
}

题目4

AtCoder E - Skiing

题意如下：

E - 滑雪

AtCoder 滑雪场有\(N\)个开放区，分别是Space 1， Space 2，...，Space N. Space \(i\) 的海拔是\(H_i\)，有\(M\)个斜坡双向连接两个Space. 第\(i(1 \leq i \leq M)\)个斜坡连接Space \(U_i\)和\(V_i\). 在任意两个空间之间使用一些斜坡是可能的。Takahashi仅通过斜坡从一个Space通过另一个Space. 每次通过一个斜坡他的幸福感改变. 具体地说，当他使用斜坡从Space \(X\) 到 Space \(Y\)，他的幸福感变化如下:

如果Space \(X\)的海拔严格高于 Space \(Y\)，他的幸福感增加\(H_X - H_Y\).
如果Space \(X\)的海拔严格低于 Space \(Y\)，他的幸福感下降\(2 \times (H_Y - H_X)\).
如果Space \(X\)的海拔等于 Space \(Y\)，他的幸福感不变.

幸福感可能是负值.
起初，Takahashi在Space 1,并且他的幸福感是0，找到他在通过任意数量（可能是0）的斜坡之后最大可能的幸福感，停止在任何Space.

数据范围：

\(2 \leq N \leq 2 \times 10^5\)
\(N - 1 \leq M \leq min(2 \times 10^5, \frac {N(N - 1)}{2})\)
\(0 \leq H_i \leq 10^8 (1 \leq i \leq N)\)
\(1 \leq U_i < V_i \leq N (1 \leq i \leq M)\)
\((U_i,V_i) \neq (U_j,V_j) \quad if \quad i \neq j\)
输入的所有值是整数
在任意两个Space之间使用一些斜坡是可能的(重边)。

输入：

N  M
H1 H2 ... HN
U1 V1
U2 V2
.
.
.
UM VM

输出：
打印答案。

样例输入1:

样例输出1：

样例解释：

如果 Takahashi 从 Space 1 -> Space 3 -> Space 4,他的幸福感变化如下：

当他从Space1(海拔10)到Space3(海拔12)，他的幸福感下降\(2 \times (12 - 10) = 4\)，幸福感变为\(-4\).
当他从Space3(海拔12)到Space4(海拔5)他的幸福感上升\(12 - 5 = 7\),并且变为了(-4 + 7 = 3)

如果他结束滑雪，最终的幸福感是3，这是最大可能的值。

样例输入2:

2 1
0 10
1 2

样例输出2：

他一点不移动的幸福感最大。

题解如下

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = INT_MAX;
struct edge{
    int v, w;
};
LL dist[N];
int h[N];
bool st[N];
int n, m;
vector<edge> e[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
void dijkstra(int s){
    for(int i = 0; i <= n; i ++ ) dist[i] = INF;
    dist[s] = 0;
    q.push({0, s}); // PII = {dist, edge} edge 到点 s 的距离dist
    while(q.size()){
        auto t = q.top();
        q.pop();
        int u = t.second;
        if(st[u]) continue;
        st[u] = true;
        for(auto &edge : e[u]){
            int v = edge.v, w = edge.w;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    int u, v;
    while(m -- ){
        scanf("%d%d", &u, &v);
        if(h[u] > h[v]){ // h[u] > h[v] 
            e[u].push_back({v, 0});
            e[v].push_back({u, h[u] - h[v]});
        }else{ // h[v] > h[u] 
            e[v].push_back({u, 0});
            e[u].push_back({v, h[v] - h[u]});
        }
    }
    dijkstra(1);
    LL ans = 0;
    for(int i = 1; i <= n; i ++ ){
        if(dist[i] == INF) continue;
        ans = max(ans, -(dist[i] - h[1] + h[i]));
    }
    printf("%lld\n", ans);
    return 0;
}

2. `Bellman-Ford`算法

题目1

Luogu P3385 【模板】负环

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, INF = 0x3f3f3f3f;
struct edge{
    int v, w;
};
vector<vector<edge>> e(N);
int dist[N], cnt[N]; // cnt 表示点i距离远点的边数
bool st[N];
queue<int> q;
int T, n, m;
bool bellman_ford(int s){
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    bool flag; // 是否松弛
    for(int i = 1; i <= n; i ++ ){
        flag = false;
        for(int u = 1; u <= n; u ++ ){
            if(dist[u] == INF) continue;
            for(auto const &edge : e[u]){
                int v = edge.v, w = edge.w;
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    flag = true;
                }
            }
        }
        if(!flag) break;
    }
    return flag;
}
int main(){
    scanf("%d", &T);
    int a, b, c;
    while(T -- ){
        e.clear();
        e.resize(N);
        scanf("%d%d", &n, &m);
        while(m -- ){
            scanf("%d%d%d", &a, &b, &c);
            if(c >= 0) e[b].push_back({a, c});
            e[a].push_back({b, c});
        }
        printf("%s\n", bellman_ford(1) ? "YES" : "NO");
    }
    return 0;
}

3. `SPFA`算法

题目1

Luogu P3385 【模板】负环

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, INF = 0x3f3f3f3f;
struct edge{
    int v, w;
};
vector<vector<edge>> e;
int dist[N], cnt[N];
bool st[N];
queue<int> q;
int T, n, m;
bool spfa(int s){
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    st[s] = true;
    q.push(s);
    while(q.size()){
        int u = q.front();
        q.pop();
        st[u] = false;
        for(auto const &edge : e[u]){
            int v = edge.v, w = edge.w;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n) return true;
                if(!st[v]) q.push(v), st[v] = true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d", &T);
    while(T -- ){
        e.clear();
        e.resize(N);
        // 清空 q
        while(!q.empty()) q.pop();
        memset(cnt, 0, sizeof cnt);
        memset(st, 0, sizeof st);
        scanf("%d%d", &n, &m);
        int a, b, c;
        while(m -- ){
            scanf("%d%d%d", &a, &b, &c);
            if(c >= 0) e[b].push_back({a, c});
            e[a].push_back({b, c});
        }
        printf("%s\n", spfa(1) ? "YES" : "NO");
    }
    return 0;
}

题目2

TODO

4. `Floyd`算法

题目1

AcWing 854. Floyd求最短路

#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, q;
void floyd(){
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    int a, b, c;
    while(m -- ){
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    floyd();
    while(q -- ){
        scanf("%d%d", &a, &b);
        if(g[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", g[a][b]);
    }
    return 0;
}

图论

注意：本文图文并茂

1. Dijkstra算法

题目1

题目2

题目3

题目4

题解如下

AC代码如下：

2. Bellman-Ford算法

题目1

3. SPFA算法

题目1

题目2

4. Floyd算法

题目1

1. `Dijkstra`算法

2. `Bellman-Ford`算法

3. `SPFA`算法

4. `Floyd`算法