自动搬运

查看原文

来自洛谷，原作者为

	Rigel 苍山负雪，明烛天南。|| 高二现役 OIer。

搬运于2025-08-24 21:45:04，当前版本为作者最后更新于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$，则有如下状态转移方程：

$$\begin{cases} f_u \gets \max(f_u,t_2+a_u),\\ g_v \gets \max(g_v,t_1+b_v). \end{cases} $$

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

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

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

代码

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