模拟赛题讲解[3]

来自 Roundgod 2022-07-26 noi.ac #2679

题目描述：

给定一个无向图 $G=(V,E)$ ，其中顶点个数 $|V|=n$ ，边数 $|E|=m$ 。顶点编号为 $1−N$，边的编号为 $1−M$ 。其中 $i$ 号顶点有一个权值 $h_i$ .

你现在可以从 $1$ 号顶点开始沿着图上的边行走。你初始时的得分为 $0$ ，当你经过一条边 $(u,v)$ 时，你的得分会如下更新:

1.如果 $h_u>h_v$ ，你的得分会增加 $h_u−h_v$ 。

2.如果 $h_u<h_v$ ，你的得分会减少 $2(h_v−h_u)$ 。

3.如果 $h_u=h_v$，你的得分会不变.

你想要知道，经过任意行走后(也可以不行走)，你可以得到的最大得分是多少?

输入格式：

输入第一行包含 $3$ 个整数 $n,m$ ，分别表示图的顶点数和图的边数。

接下来一行包含 $n$ 个整数 $h_1,h_2,\dots ,h_n$ ，表示每个顶点的初始权值。

接下来 $m$ 行，每行 $u_i,v_i(1\le u_i,v_i\le n,u_i\ne v_i)$ ，表示第 $i$ 条边。

输入格式：

在一行中输出一个数，表示你可以得到的最大得分。

输入1：

输出1：

输入2：

2 1
0 10
1 2

输出2：

数据范围：

对于 $30\%$ 的数据，$1\le n\le 200,~1\le m\le 1000,~1\le h_i\le 10^9$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5,~1\le m\le 2\times 10^5,~1\le h_i\le 10^{18}$

题解：

不难发现这个图就是要找个最长路

常见的trick就是把边权取反后跑最短路

注：这里以及下文中的取反指变成其相反数

而这道题的边权其实很好推

$w(u,v)=\begin{cases} 2h_u-2h_v,&h_u<h_v \\\\0,&h_u=h_v \\\\h_u-h_v,&h_u>h_v \end{cases}$

注意到会有负权边，且 $n \le 2 \times 10^5$

直接用spfa或者dijkstra肯定是不行的（虽然数据没成功卡掉）

还记得什么“黑科技”可以让 $\text{Dijkstra}$ 跑负权图吗？

答案是势能函数，也叫权重函数，思想来源于 Johnson 全源最短路算法

说的简单一点，一般势能函数就是把负权改成非负权，然后跑 $\text{Dijkstra}$

在本题中，我们可以设

$w^{\prime}(u,v)=w(u,v)-(h_u-h_v)$

于是

$w^{\prime}(u,v)=\begin{cases} h_u-h_v,&h_u<h_v \\\\0,&h_u\ge h_v \end{cases}$

不难发现，此时 $w^{\prime}(u,v) \le 0$ 恒成立

设 $d_i=f_i+h_i-h_1$ ，其中 $f_i$ 为我们要求的最大分数（最长路长度）

可以发现，如果我们要求出 $f_i$ ，就需要求出 $d_i$

而这个 $d_i$ 就是使用势能函数作边权后 $1$ 到 $i$ 的最长路

还记得刚刚的trick吗？我们要求的是边权取反后的最短路

这样我们把 $-w^{\prime}(u,v)$ 加入，跑个最短路，就能求出答案了

此时求出的其实是 $d^{\prime}_i=-f_i-h_i+h_1$

移项得 $f_i=h_1-h_i-d^{\prime}_i$

时间复杂度 $O(n \log m)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e5+15)

int n,m,pos=1,h[N],d[N],head[N],vis[N];
struct Edge{int u,v,w,next;}e[N<<1];
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
priority_queue<node> q;
void dijkstra(int st)
{
    for(int i=1; i<=n; i++) d[i]=INF;
    d[st]=0; q.push({st,0});
    while(!q.empty())
    {
        int u=q.top().u; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(d[v]>d[u]+e[i].w)
            {
                d[v]=d[u]+e[i].w;
                q.push({v,d[v]});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        if(h[u]<=h[v]) addEdge(u,v,h[v]-h[u]);
        else addEdge(u,v,0);
        if(h[v]<=h[u]) addEdge(v,u,h[u]-h[v]);
        else addEdge(v,u,0);
    }
    dijkstra(1);
    int res=0;
    for(int i=1; i<=n; i++)
        res=max(res,h[1]-h[i]-d[i]);
    cout << res << '\n';
    return 0;
}