题解 P6822 【[PA2012]Tax】

· · 题解

原题链接：P6822 [PA2012] Tax。

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

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

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

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

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

  4. 将一个点出发的所有边按照边权排序，对于排序后相邻的两条边 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 均为原图中节点编号。

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

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

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

就这样。

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;
}