项链题解

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