自动搬运

查看原文

来自洛谷，原作者为

	STDquantum 尝试用唯物的角度去理解，瞬间就是永恒。

搬运于2025-08-24 22:24:20，当前版本为作者最后更新于2020-10-19 22:19:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接：P6822 [PA2012] Tax。

虽然说是套路题，但是如果是第一次做的话也还是有些困难的，于是我就来用图形形象化地说明一下。只是便于理解，并没有正解的推导过程。

直接说做法（连边均为有向边）：

0. 建立超级源点 $s$ 和超级汇点 $t$，并且无向边拆成有向边、化边为点。

1. 对于所有从 $1$ 出发的边，从 $s$ 向这些边对应的点连权值为原图权值的边；对于所有结束于 $n$ 的边，从这些边对应的点向 $t$ 连权值为原图权值的边。

2. 所有边向自己的反向边连权值为原图权值的边。

3. 将一个点出发的所有边按照边权排序，对于排序后相邻的两条边 $i$ 与 $i+1$，从 $i$ 向 $i+1$ 连权值为 $w_{i+1}-w_i$ 的边，从 $i+1$ 向 $i$ 连权值为 $0$ 的边。

到此连边过程就结束了，从 $s$ 跑单源最短路（不能用 SPFA！！！），$dis_t$ 即为题中所求的值。

现在举一个简单的例子：

边上方的数字代表从左到右的有向边的编号，边下方的数字代表从右到左的有向边的编号。

按照所给方式连边后的图（节点编号对应上图边的编号）：

现在我们来看一条合法的从 $s$ 到 $t$ 的路径：$s\rightarrow 1\rightarrow 5\rightarrow3\rightarrow t$。

为防止语义冲突，在原图中的边定义为 $(i,j)$，$i$ 与 $j$ 均为原图中节点编号。

• $s\rightarrow 1$ 的边权为 $(1,2)$ 边权，代表从 $1$ 出来时的代价。
• $1\rightarrow5\rightarrow3$ 中，前者边权为 $(1,2)$ 边权，后者边权为 $(1,2), (2,4)$ 的边权差距。此处说为差距是因为不清楚两者之间的大小关系，若 $(1,2)$ 大于 $(2,4)$，那么 $5\rightarrow3$ 的权值为 $0$，合到一块 $1\rightarrow5\rightarrow3$ 的权值就为 $(1,2)$ 的边权；若 $(1,2)$ 小于 $(2,4)$，那么 $5\rightarrow3$ 的权值为 $w_{(2,4)}-w_{(1,2)}$，合到一块 $1\rightarrow5\rightarrow3$ 的权值就为 $(2,4)$ 的边权。
• $3\rightarrow t$ 的边权为 $(2,4)$ 边权，代表到 $n$ 结束的代价。

引入不同边的差值可以让我们直接计算出最大边权，从而避免了讨论的情况。

新图中的点分为了三个集合，源汇点、正向边和反向边。

在新图中可以发现如下性质：

• 当走源汇点和正向边之间的边时，所计算的是离开 $1$ 或来到 $n$ 的代价；
• 当走正向边和反向边内部的边时（其实就是一个点出来的边），代表着反悔操作，也就是换了一条边走。
• 当在正向和反向边之间横跳时（如 $1\rightarrow5\rightarrow3$），代表又走过了一个节点，并计算了最大边的权值。

就这样。

C++98（去掉了C++11的特性和一些可能会让人迷惑的地方）：码风有一（亿）点毒瘤，可以拿来对拍。

云剪贴板。

C++11版本：

#include <bits/stdc++.h>
using namespace std;

namespace Sweet {

template <typename T> inline void read(T &x) {
    char ch;
    int f = 1;
    while (ch = getchar(), ch > '9' || ch < '0')
        if (ch == '-') f = -1;
    x = (ch ^ 48);
    while (ch = getchar(), ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48);
    x *= f;
}
template <typename T> inline void write(T x) {
    static int stk[100], top = 0;
    if (x == 0) return (void)putchar('0');
    if (x < 0) x = -x, putchar('-');
    while (x) stk[++top] = x % 10, x /= 10;
    while (top) putchar(stk[top--] + '0');
}

typedef long long ll;
const int N = 1e5 + 10, V = 4e5 + 10;

basic_string<pair<int, int> > e[V];
inline void add(int x, int y, int z) { e[x] += {y, z}; } // +=相当于push_back

struct T {
    int x;
    ll dis;
    T(int X, ll Dis) : x(X), dis(Dis) {}
    bool operator<(const T &rhs) const { return dis > rhs.dis; }
};
extern int s, t;
ll dis[V];
ll Dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<T> q;
    q.emplace(s, dis[s] = 0);
    static T u(0, 0);
    while (!q.empty()) {
        u = q.top(), q.pop();
        if (u.dis != dis[u.x]) continue;
        for (auto v : e[u.x]) {
            if (dis[v.first] > u.dis + v.second) {
                q.emplace(v.first, dis[v.first] = u.dis + v.second);
            }
        }
    }
    return dis[t];
}

struct Edge {
    int v, w, id;
    bool operator<(const Edge &rhs) const { return w < rhs.w; }
};
basic_string<Edge> g[N]; // 似乎比vector要快一点？
basic_string<Edge>::iterator it;

int n, m, s = 0, t = 1;
inline void main() {
    read(n), read(m);
    for (int i = 1, a, b, c; i <= m; ++i) {
        read(a), read(b), read(c);
        g[a] += {b, c, i << 1}, g[b] += {a, c, i << 1 | 1}; // 编号方式：异或1得到反向边
    }
    for (int i = 1; i <= n; ++i) {
        if (g[i].empty()) continue; // 后面迭代器的写法要求不能为空，直接用下标遍历不用判
        sort(g[i].begin(), g[i].end());
        for (auto j : g[i]) {
            add(j.id ^ 1, j.id, j.w);
            (i == 1) && (add(s, j.id, j.w), 0); // 短路表达式 = if
            (j.v == n) && (add(j.id, t, j.w), 0);
        }
        for (it = g[i].begin(), ++it; it != g[i].end(); ++it) {
            add(it->id, (it - 1)->id, 0);
            add((it - 1)->id, it->id, it->w - (it - 1)->w);
        }
    }
    write(Dijkstra());
}

}    // namespace Sweet

int main() {
    Sweet::main();
    return 0;
}