题目描述
分析与思路
记忆化搜索+正反向建边
题目意思是寻找不相交的两条路径,其中一条路径的宝石的总价值最大
所以我们可以正向建边通过记忆化搜索出宝石数最多的路径,再反向建边搜索另一条路径
其中ma数组表示从i出发的能获得最大价值的钻石
AC代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; #define ll long long struct node{ll ne,to;}; ll n,m,cn,cn1,a[N],he1[N],he[N],de[N],de1[N],dp[N],dp1[N],vi[N],vi1[N],ma[N],ma1[N]; node w[N],w1[N]; //ma数组表示从i出发的能获得最大价值的钻石 void dfs(ll x) //记忆化搜索 { vi[x]=1;dp[x]=a[x]; for(ll i=he[x];i!=-1;i=w[i].ne) { ll to=w[i].to; if(!vi[to]) dfs(to); dp[x]=max(dp[x],dp[to]+a[x]); ma[x]=max(ma[x],ma[to]); } ma[x]=max(ma[x],dp[x]); } void dfs1(ll x) { vi1[x]=1;dp1[x]=a[x]; for(ll i=he1[x];i!=-1;i=w1[i].ne) { ll to=w1[i].to; if(!vi1[to]) dfs1(to); dp1[x]=max(dp1[x],dp1[to]+a[x]); ma1[x]=max(ma1[x],ma1[to]); } ma1[x]=max(ma1[x],dp1[x]); } void add(ll x,ll y)//链式前向星 { w[++cn].to=y; w[cn].ne=he[x]; he[x]=cn; } void add1(ll x,ll y) { w1[++cn1].to=y; w1[cn1].ne=he1[x]; he1[x]=cn1; } signed main() { scanf("%lld%lld",&n,&m); memset(he,-1,sizeof(he)); memset(he1,-1,sizeof(he1)); for(ll i=1;i<=n;++i) scanf("%lld",&a[i]); for(ll i=1;i<=m;++i) { ll x,y; scanf("%lld%lld",&x,&y); ++de[y];add(x,y);//正向建图 ++de1[x];add1(y,x);//反向建图 } ll an=0,an1=0; for(ll i=1;i<=n;++i){ if(!de[i]) dfs(i),an=max(an,ma[i]); if(!de1[i]) dfs1(i); } for(ll i=1;i<=n;++i){ for(ll j=he[i];j!=-1;j=w[j].ne)//遍历一条边的两端 { ll to=w[j].to,te,tem; te=ma[to],tem=ma1[i]; if(te<tem)swap(te,tem); if(te>an) an=te,an1=tem; else if(te==an) an1=max(an1,tem); } } printf("%lld %lld\n",an,an1); return 0; }