跳到主要内容

琪亚娜与虚数之海

· 阅读需 2 分钟

我认为是比上一个题更简单的题目，我们容易想到每进入一个SCCSCC我们可以选择完所有的点。

所以TarjanTarjan缩点后保证DAGDAG再拓扑跑一遍就行。

时间复杂度：O(n+m)O(n+m)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define QAQ return

const int N=1e5+10;

int idx, num;
int dfn[N], low[N];
int group[N], dge[N];
bool in[N];
ll sum[N], val[N], f[N];
stack< int > stk;
vector< int > rode[N], sp_rode[N];

inline void dfs( int p )
{
	dfn[p]=low[p]=++idx;
	in[p]=true;
	stk.push( p );
	for( auto &x:rode[p] )
	{
		if( !dfn[x] )
		{
			dfs( x );
			low[p]=min( low[p],low[x] );
		}
		else if( in[x] ) low[p]=min( low[p],dfn[x] );
	}
	if( dfn[p] == low[p] )
	{
        num++;
		while( stk.top() != p )
		{
			sum[num]+=val[stk.top()];
			group[stk.top()]=num;
			in[stk.top()]=false;
			stk.pop();
		}
		sum[num]+=val[stk.top()];
		group[stk.top()]=num;
		in[stk.top()]=false;
		stk.pop();
	}
}

int main()
{
    // freopen( "txt.in","r",stdin );
    // freopen( "txt.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ); cout.tie( nullptr );
	int n, m;
    cin>>n>>m;
    for( int i=1;i<=n;i++ ) cin>>val[i];
    for( int i=1, u, v;i<=m;i++ )
        cin>>u>>v,
        rode[u].push_back( v );
    dfs( 1 );
    for( int u=1;u<=n;u++ ) for( auto &v:rode[u] ) if( group[u] != group[v] )
        sp_rode[group[u]].push_back( group[v] ), dge[group[v]]++;
    queue< int > topsort;
    memset( f,0xcf,sizeof f );
    topsort.push( group[1] );
    f[group[1]]=sum[group[1]];
    ll ans=0;
    while( !topsort.empty() )
    {
        auto p=topsort.front();
        topsort.pop();
        ans=max( ans,f[p] );
        for( auto &x:sp_rode[p] )
        {
            f[x]=max( f[x],f[p]+sum[x] );
            if( !( --dge[x] ) ) topsort.push( x );
        }
    }
    cout<<ans;
	QWQ
}