TIOJ 1744 [APIO '09] ATM ( SCC + DP )
1744 - [APIO '09] ATM | TIOJ INFOR Online Judge
題意:給你 n ≤ 5e5 個節點,每個節點都有權重,有些節點是酒吧,接著給你 m ≤ 5e5 個有向邊。給你一個起點,求最後停在一個酒吧( 經過的酒吧可以不要理會 ) 的經過的節點權重總和最大值。同一個節點可以被造訪多次,但同一個節點的權重只能被取一次。
寫過Strong connected components - 0w1就覺得這題挺水的。思路很明白,就是先求出所有強連通分量,做縮環的動作之後對於所有強連通分量建有向邊( 縮環 ),就變成在DAG上的動態規劃問題了。這部分用記憶化搜尋DP亂搞就出來了。讓我卡一下子的反而是實作的小細節,像是該冠上 sccno[ ]的沒冠上,不需要的反而用上了什麼的。還有就是到最後一刻才發現我用的是節點的 is_bar[ ] 而非對於強連通分量是否可停駐的 can_stop[ ]。。
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; const int MAXM = 5e5 + 5; const int MAXV = 4000 + 4; const int INF = 2e9 + 1; // careful for overflow #define int long long int n, m; vector<int> G[ MAXN ]; vector<int> RG[ MAXN ]; // reversed G int val[ MAXN ]; int s, p; int is_bar[ MAXN ]; vector<int> stk1; int vis1[ MAXN ]; void dfs1(int u){ vis1[ u ] = 1; for(int v: G[ u ]) if( !vis1[ v ] ) dfs1( v ); stk1.push_back( u ); } int scc_cnt, sccno[ MAXN ]; // 1 based void dfs2(int u){ sccno[ u ] = scc_cnt; for(int v: RG[ u ]) if( !sccno[ v ] ) dfs2( v ); } void getSCC(){ for(int u = 1; u <= n; ++u) if( !vis1[ u ] ) dfs1( u ); for(int i = stk1.size() - 1; i >= 0; --i) if( !sccno[ stk1[ i ] ] ) ++scc_cnt, dfs2( stk1[ i ] ); } int sccval[ MAXN ]; int can_stop[ MAXN ]; vector<int> dp_edge[ MAXN ]; int memo[ MAXN ]; int dp(int x){ if( memo[ x ] != -1 ) return memo[ x ]; if( G[ x ].empty() && !can_stop[ x ] ) return memo[ x ] = -INF; int res = -INF; if( can_stop[ x ] ) res = sccval[ x ]; for(int y: dp_edge[ x ]){ // printf("%d -> %d\n", x, y); res = max( res, sccval[ x ] + dp( y ) ); } // printf("memo[ %d ] = %d\n", x, res); return memo[ x ] = res; } void solve(){ getSCC(); for(int u = 1; u <= n; ++u){ sccval[ sccno[ u ] ] += val[ u ]; can_stop[ sccno[ u ] ] |= is_bar[ u ]; for(int v: G[ u ]){ // printf("%d -> %d : %d -> %d\n", u, v, sccno[ u ], sccno[ v ]); if( sccno[ u ] != sccno[ v ] ){ // printf("%d -> %d\n", sccno[ u ], sccno[ v ]); dp_edge[ sccno[ u ] ].push_back( sccno[ v ] ); } } } // for(int i = 1; i <= scc_cnt; ++i) printf("sccval[ %d ] : %d\n", i, sccval[ i ]); memset( memo, -1, sizeof(memo) ); int ans = dp( sccno[ s ] ); cout << ans << "\n"; } signed main(){ ios::sync_with_stdio( false ); cin >> n >> m; for(int i = 0; i < m; ++i){ int u, v; cin >> u >> v; // scanf("%d%d", &u, &v); G[ u ].push_back( v ); RG[ v ].push_back( u ); // 1 base } for(int u = 1; u <= n; ++u) cin >> val[ u ]; // scanf("%d", &val[ u ]); cin >> s >> p; // scanf("%d%d", &s, &p); for(int i = 0; i < p; ++i){ int u; cin >> u; // scanf("%d", &u); is_bar[ u ] = 1; } solve(); return 0; }