模拟赛题讲解[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;
}