0w1

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