第一节 最短路

Contents

一般最短路

Floyd 传递闭包

可以使用 bitset 优化:

例题:洛谷 P4306[JSOI2010]连通数

题目大意:

给一个 n 个点的有向图,其连通数指图中可达顶点对个的个数(包括自己和自己)。求图中的连通数

问题分析:

可以直接 Floyd 传递闭包搞。

如果上面做法被卡,可以先用 Tarjan 缩点,然后在 DAG 上 BFS 或者 DFS 找出每个点可以通向的点。这个过程同样可以用 bitset 来优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 50;
int n;
string s;

bitset<N> l[N];
void Floyd() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (l[j][i]) {
                l[j] |= l[i];
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            l[i][j] = s[j] - '0';
        }
        l[i][i] = 1;
    }
    Floyd();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += l[i].count();
    }
    printf("%d\n", ans);
    return 0;
}

Dijkstra

typedef pair<int, int> pii;
#define mp make_pair
int dis[N], vis[N];
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int rt) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    while (!pq.empty()) pq.pop();
    dis[rt] = 0;
    pq.push({0, rt});
    while (!pq.empty()) {
        pii t = pq.top(); pq.pop();
        if (vis[t.second]) continue;
        vis[t.second] = 1;
        for (int i = head[t.second]; i; i = e[i].nex) {
            int to = e[i].to;
            if (dis[to] > t.first + e[i].w) {
                dis[to] = t.first + e[i].w;
                pq.push(mp(dis[to], to));
            }
        }
    }
}

例题:2019ICPC银川 H. Delivery Route

题目大意:

给你一幅图,有 x 条无向边和 y 条有向边。其中无向变的权值均为正,有向边的权值可能为负。保证如果从 a_ib_i 有一条有向边,则不存在 b_ia_i 的路径。给你一个出发点,求单源最短路径。

分析:

首先,由于存在负权路径,直接 Dijkstra 显然不可取。考虑使用 spfa,又很容易被卡掉。我们观察题目比起裸的单源最短路径有何区别:将无向图的每个联通块缩成点后,形成了一个拓扑图!

于是我们可以先用 dfs 对所有的联通块染色,按照拓扑排序的顺序,对每个联通块内部用 Dijkstra。如果一条边连向另一个联通块,就更新该点的最短路径(但不加入堆中)。对一个联通块做完 Dijkstra,我们遍历其中所有点,对其连边所指向的联通块度数减 1;遍历到一个新的联通块,我们把所有最短路径不为 INF 的点加入优先队列。

#include <bits/stdc++.h>
using namespace std;
int n, x, y, s;
const int N = 2e5 + 50;
typedef pair<int, int> pii;
#define mp make_pair

int head[N], tot;
struct Edge {
    int nex, to, w;
}e[N];
void addedge(int a, int b, int c) {
    e[++tot] = {head[a], b, c};
    head[a] = tot;
}
void add(int a, int b, int c) {
    addedge(a, b, c);
    addedge(b, a, c);
}

vector<int> bel[N];
int co[N], cnt; //联通块的颜色、联通块的数量
void dfs(int v, int col) { //dfs给联通块染色
    co[v] = col;
    bel[col].push_back(v);
    for (int i = head[v]; i; i = e[i].nex) {
        int to = e[i].to;
        if (!co[to]) dfs(to, col);
    }
}

int deg[N], dis[N];//每个联通块的入度、单源最短路径
int vis[N];
queue<int> qu;//拓扑排序:入度为0的联通块入队
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int S) {
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    for (int i = 1; i <= cnt; i++) if (!deg[i]) qu.push(i);
    while (!qu.empty()) { //topological-sort
        int u = qu.front(); qu.pop();
        int sz = (int)bel[u].size();
        for (int i = 0; i < sz; i++) if (dis[bel[u][i]] < 1e9) {
            pq.push(mp(dis[bel[u][i]], bel[u][i]));
        }
        while (!pq.empty()) { //Dijkstra
            int x = pq.top().second; pq.pop();
            if (vis[x]) continue;
            vis[x] = 1;
            for (int i = head[x]; i; i = e[i].nex) {
                int to = e[i].to;
                if (co[x] == co[to] && dis[to] > dis[x] + e[i].w) {
                    dis[to] = dis[x] + e[i].w;
                    pq.push(mp(dis[to], to));
                }
                if (co[x] != co[to]) {
                    dis[to] = min(dis[to], dis[x] + e[i].w);
                }
            }
        }
        for (int x = 0; x < sz; x++) {
            int y = bel[u][x];
            for (int i = head[y]; i; i = e[i].nex) {
                int to = e[i].to;
                if (co[y] != co[to]) {
                    deg[co[to]]--;
                    if (!deg[co[to]]) qu.push(co[to]);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &x, &y, &s);
    for (int i = 1, a, b, c; i <= x; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    for (int i = 1; i <= n; i++) if(!co[i]) dfs(i, ++cnt);
    for (int i = 1, a, b, c; i <= y; i++) {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        deg[co[b]]++;
    }
    Dijkstra(s);
    for(int i = 1; i <=n; i++) {
        if (dis[i] > 1e9) puts("NO PATH");
        else printf("%d\n", dis[i]);
    }
    return 0;
}

spfa

queue<int> q;
void spfa(int rt) {
    memset(dis, 0x3f, sizeof(dis));
    q.push(rt); vis[rt] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop(); vis[x] = 0;
        for (int i = head[x]; i; i = e[i].nex) {
            int to = e[i].to;
            if (dis[to] > e[i].w + dis[x]) {
                dis[to] = e[i].w + dis[x];
                if (!vis[to]) {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
}

Johnson全源最短路

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define mp make_pair
const int INF = 1e9;
const int N = 3e3 + 10;
const int M = 1e4 + 50;
int n, m;

int head[N], tot;
struct Edge {
    int nex, to, dis;
}e[M];
void add(int a, int b, int c) {
    e[++tot] = (Edge) {head[a], b, c};
    head[a] = tot;
}

int d[N], vis[N], tim[N];
queue<int> q;
bool spfa(int u) {
    memset(d, 0x3f, sizeof(d));
    d[u] = 0; vis[u] = 1;
    q.push(u);
    while (!q.empty()) {
        int v = q.front();
        q.pop(); vis[v] = 0;
        if (++tim[v] >= n) {
            return 0;
        }
        for (int i = head[v]; i; i = e[i].nex) {
            int to = e[i].to;
            if (d[to] > d[v] + e[i].dis) {
                d[to] = d[v] + e[i].dis;
                if (!vis[to]) {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    return 1;
}

int dis[N][N];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int u) {
    memset(dis[u], 0x3f, sizeof(dis[u]));
    memset(vis, 0, sizeof(vis));
    while(!pq.empty()) pq.pop();
    dis[u][u] = 0;
    pq.push(mp(0, u));
    while(!pq.empty()) {
        pii t = pq.top(); pq.pop();
        if(vis[t.second]) continue;
        vis[t.second] = 1;
        for(int i = head[t.second]; i; i = e[i].nex) {
            int to = e[i].to;
            if(dis[u][to] > t.first + e[i].dis) {
                dis[u][to] = t.first + e[i].dis;
                pq.push(mp(dis[u][to], to));
            }
        }
    }
}

int Johnson() {
    for (int i = 1; i <= n; i++) {
        add(n + 1, i, 0);
    }
    if (!spfa(n + 1)) {
        return -1;
    }
    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; i; i = e[i].nex) {
            e[i].dis += d[u] - d[e[i].to];
        }
    }
    for (int i = 1; i <= n; i++) {
        Dijkstra(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = dis[i][j] - d[i] + d[j];
        }
    }
    return 1;
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1, a, b, c; i <= m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if (Johnson() == -1) { // 有负环
        cout << "-1\n";
        return 0;
    }
    return 0;
}

变形最短路

同余最短路

题目:P3403 跳楼机

题目大意:

一共有 h 层,开始在第 1 层,有 4 种操作:向上走 x 层,向上走 y 层,向上走 z 层,回到第 1 层。问一共有多少可到达楼层。1\le h\le 2^{63}-1,1\le x,y,z\le 10^5

问题等价于求 x+y+z=k 可能 k 取值的方案数。

分析:

不妨设 x 为最小的数。对 \bmod \ x 构造同余系:设 f[i] 为到达楼层 \bmod \ x\equiv i 的最小楼层,那么 f(i)+xf(i)+2x 等等都可以到达,这一部分答案为 (h-f[i])/x+1

考虑如何计算 f[i]。对于每个 i\in[0,x-1],向 (i+y)%x 连一条 y 的边、向 (i+z)%x 连一条 z 的边,跑最短路即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define mp make_pair
const int N = 1e5 + 50;
ll h, ans;
int n = 3, a[5], x = N;

int head[N], tot;
struct Edge {
    int nex, to, w;
}e[N * 10];
void add(int a, int b, int c) {
    e[++tot] = {head[a], b, c};
    head[a] = tot;
}

ll dis[N];
int vis[N];
priority_queue< pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int u) {
    memset(dis, 0x3f, sizeof(dis));
    dis[u] = 1;
    memset(vis, 0, sizeof(vis));
    while (!pq.empty()) pq.pop();
    pq.push({1, u});
    while (!pq.empty()) {
        pii t = pq.top(); pq.pop();
        if (vis[t.second]) continue;
        vis[t.second] = 1;
        for (int i = head[t.second]; ~i; i = e[i].nex) {
            int to = e[i].to;
            if(dis[to] > t.first + e[i].w)
            {
                dis[to] = t.first + e[i].w;
                pq.push(mp(dis[to], to));
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> h;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; x = min(x, a[i]);
    }
    if (x == 1) {
        cout << h << "\n"; return 0;
    }

    memset(head, -1, sizeof(head));
    for (int i = 1; i < x; i++) {
        for (int j = 1; j <= n; j++) {
            add(i, (i + a[j]) % x, a[j]);
        }
    }
    Dijkstra(1);
    for (int i = 0; i < x; i++) {
        if (dis[i] <= h) {
            ans += (h - dis[i]) / x + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

题目:P2737 [USACO4.1]麦香牛块

题目大意:

N 个数,求它们最大的不能表示的数。

分析:

仍然构造同余系。对最小的 x 跑同余最短路,每个 dis[i]-x 的最大值即为最大不可能表示的数。

N=2\gcd(a,b)=1 时,利用上面做法,答案为 ab-a-b

概率最短路

题目:P4745 [CERC2017]Gambling Guide

题目大意:

给一张无向图,每次“买票”,从一个点随机到另一个点,可以选择走或不走。给定起点 1 和终点 n,问最小的“买票”期望次数。

分析:

从终点往前合并,满足以合并的点到达终点的期望次数都比未合并的少。

用优先队列维护没有被合并的点到终点的期望次数,记为 now。开始的时候只有 n 在队列终。每次合并 now 最小的点 p,同时更新所有能到达它的点。对于要更新的点 to,我们分成三种情况:到达已经被合并的点的加权期望步数 tmp,到达新合并点 p 的加权期望步数 \frac{nd[p].now+1}{degree},到达未合并点并返回的期望步数。我们记录下每个点所连边中,连向已被合并的个数 used,则每次更新的过程:

  1. nd[to].used++
  2. 设: t=nd[p].now,x=nd[to].now,有方程:

\begin{aligned}
x&=tmp+\frac{t+1}{degree}+\frac{degree-used}{degree}(x+1)\cr\cr
\iff x&=\frac{degree * tmp+t+1+degree-used}{used}
\end{aligned}

  1. 更新 totmp 参数:

tmp=tmp+\frac{t+1}{degree}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
int n, m;

struct Node {
    int id;
    int deg, used;
    double tmp, now;
    bool operator < (const Node &x) const {
        return now > x.now;
    }
}nd[N];

struct Edge {
    int nex, to;
}eg[N];

int head[N], tot;
void add(int a, int b) {
    eg[++tot] = (Edge){head[a], b};
    head[a] = tot;
}

int vis[N];
priority_queue<Node> pq;
void Dijkstra(int S) {
    pq.push(nd[S]);
    while (!pq.empty()) {
        int p = pq.top().id;
        pq.pop();
        if (vis[p]) continue;
        vis[p] = 1;
        double t = nd[p].now;
        for (int i = head[p]; i; i = eg[i].nex) {
            int to = eg[i].to, deg = nd[to].deg;
            if (vis[to]) continue;
            nd[to].used++;
            nd[to].now = (deg * nd[to].tmp + t + 1 + deg - nd[to].used) / nd[to].used;
            nd[to].tmp += (t + 1) / deg;
            pq.push(nd[to]);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
        nd[a].deg++; nd[b].deg++;
    }
    for (int i = 1; i <= n; i++) nd[i].id = i;
    for (int i = 1; i < n; i++) nd[i].now = 1e15;
    Dijkstra(n);
    printf("%.10lf\n", nd[1].now);
    return 0;
}

分层图最短路

例题:P4568 [JLOI2011]飞行路线

题目大意:

n 个点 m 条边的无向图,每条边有一个花费,其中有 k 次机会可以减免花费。给定起点 s 和终点 t,求最小花费。

分析:

构建分层图,每一层之间均按照正常图相连,在相邻两层之间对应边连一条花费为 0 的边。一共有 k + 1 层。
同时为了计算免费次数用不完的情况,把每层的 t 均相连。对第一层的 s 和最后一层的 t 跑最短路即可。

int main(int argc, const char * argv[]) {
    scanf("%d%d%d", &n, &m, &k);
    scanf("%d%d", &s, &t);
    s++; t++;
    for (int i = 1, a, b, c; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        a++; b++;
        add(a, b, c); add(b, a, c);
        for (int i = 1; i <= k; i++) {
            int x = (i - 1) * n + a, y = i * n + a;
            int u = (i - 1) * n + b, v = i * n + b;
            add(x, v, 0); add(u, y, 0);
            add(y, v, c); add(v, y, c);
        }
    }
    for (int i = 1; i <= k; i++) {
        int x = (i - 1) * n + t, y = i * n + t;
        add(x, y, 0);
    }
    Dijkstra(s);
    printf("%d\n", dis[k * n + t]);
    return 0;
}

差分约束

题目大意:

给出一组包含 m 个不等式,有 n 个未知数的形如:

\begin{cases}
x_{i_1}-x_{j_1}\leq y_1 \cr x_{i_2}-x_{j_2} \leq y_2 \cr \cdots\cr x_{i_m} – x_{j_m}\leq y_m
\end{cases}

的不等式组,求任意一组满足这个不等式组的解。

分析:

  1. 从每个 ji 连一条长为 y 的边;新增一个超级源点向每个点连一条长为 0 的边,跑最短路。
    如果有负环则无解;否则每个变量的答案为其到超级源点的最短路径。这样输出的答案为各点的最小值。
int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b, w; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &w);
        add(b, a, w);
    }
    for (int i = 1; i <= n; i++) {
        add(n + 1, i, 0);
    }
    if (!spfa(n + 1)) puts("NO");
    else for (int i = 1; i <= n; ++i) {
        printf("%d%c", dis[i], i == n ? '\n' : ' ');
    }
    return 0;
}
  1. 从每个 ij 连一条长为 -y 的边;新增一个超级源点向每个点连一条长为 0 的边,跑最长路。
    如果有正环则无解;否则每个变量的答案为其到超级源点的最短路径。这样输出的答案为各点的最大值。
    注意写最长路时,spfa 中的 dis 要赋初值 -1,小于号变大于号即可。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇