Description

题目链接

题目大意：有 $n$ 个点，$m$ 条边的无向图，每个点有一个值 $h_i$。以 $1$ 号点为起点，初始开心值为 $0$，当经过一条边 $(u, v)$ 时，如果 $h_u \ge h_v$，开心值加上 $h_u - h_v$，否则减去 $2(h_v - h_u)$，问最大开心值是多少。$1 \le n, m \le 2 \times 10^5$。

Solution

原问题可以看作是图上求最长路，而且它的边权设置很巧妙，不会出现一个环让开心值一直增加。

如果我们将所有边权取相反数，原问题就变为了图上求最短路。

图中可能存在负权边，因此不能使用 Dijkstra。考虑 Johnson 分配势能的过程，如果我们把 $h_i$ 当作每个点的势能，正好符合 Johnson 的要求，且每条边的边权都变为了非负值。

然后用 Dijkstra 求最短路即可。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Node {
    int pos;
    LL dis;
    friend bool operator < (const Node &a, const Node &b) {
        return a.dis > b.dis;
    }
};

struct Edge {
    int to, w;
};

std::priority_queue<Node> q;
std::vector<Edge> g[200010];
LL h[200010], d[200010];
LL ans;
int n, m;
bool vis[200010];

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)    read(h[i]), d[i] = 1e18;
    for (int i = 1, u, v; i <= m; ++i) {
        read(u), read(v);
        g[u].push_back((Edge){v, std::max(h[v] - h[u], 0LL)});
        g[v].push_back((Edge){u, std::max(h[u] - h[v], 0LL)});
    }
    q.push((Node){1, 0});
    d[1] = 0;
    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        if (vis[now.pos])    continue;
        vis[now.pos] = true;
        for (auto i : g[now.pos]) {
            if (d[i.to] > d[now.pos] + i.w) {
                d[i.to] = d[now.pos] + i.w;
                q.push((Node){i.to, d[i.to]});
            }
        }
    }
    for (int i = 1; i <= n; ++i)    ans = std::max(ans, h[1] - h[i] - d[i]);
    printf("%lld\n", ans);
    return 0;
}