P3077 [USACO13FEB] Route Design G

Rigel · 2025-06-24 20:29:51 · 题解

思路

DP。

首先将每条边按左端点排序，若左端点相同则按右端点排序。这保证了状态转移时路径不交叉。

设 a_i 表示左岸第 i 个点的点权，b_i 表示右岸第 i 个点的点权。

设 f_i 表示以左岸第 i 个点为终点的的路径的最大点权和，g_i 表示以右岸第 i 个点为终点的路径的最大点权和。初始时所有 f_i=a_i，g_i=b_i。

对于每一条边，设其左右两端分别为 u、v。令 t_1 \gets f_u，t_2 \gets g_v，则有如下状态转移方程：

用更新后的 f_u 与 g_v 更新最终答案。

在每个状态更新前已经考虑了所有前驱状态，因此最终答案必然最优。

时间复杂度：将边排序 \mathcal{O}(r \log r)，DP \mathcal{O}(r)，整体复杂度为 \mathcal{O}(r \log r)。

Code

#include<bits/stdc++.h>
#define int long long
#define maxn 40010
#define maxe 100010

using namespace std;

int n,m,r,a[maxn],b[maxn],f[maxn],g[maxn],ans;

struct edge{
    int u,v;
    bool operator<(const edge &tt)const{return (u^tt.u)?(u<tt.u):(v<tt.v);}
}e[maxe];

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

signed main(){
    n=read(),m=read(),r=read();
    for(int i=1;i<=n;i++)a[i]=f[i]=read(),ans=max(ans,a[i]);
    for(int i=1;i<=m;i++)b[i]=g[i]=read(),ans=max(ans,b[i]);
    for(int i=1;i<=r;i++)e[i].u=read(),e[i].v=read();
    sort(e+1,e+r+1);
    for(int i=1;i<=r;i++){
        int t1=f[e[i].u],t2=g[e[i].v];
        f[e[i].u]=max(f[e[i].u],t2+a[e[i].u]);
        g[e[i].v]=max(g[e[i].v],t1+b[e[i].v]);
        ans=max(ans,max(f[e[i].u],g[e[i].v]));
    }
    printf("%lld\n",ans);
    return 0;
}