P3627 抢掠计划

问题

P3627 [APIO2009] 抢掠计划
城市中的道路都是单向的，每个路口都有一台存放一定现金的 ATM，部分路口还设有酒吧。强盗从指定的市中心出发，可以重复经过路口和道路，但每台 ATM 的现金只能抢一次；他最终必须到达某个酒吧，要求计算最多能够抢到多少钱。

数据规模：$N,M\le 5\times 10^5$，点权不超过 $4000$。

要做一个类似 DP 的问题，不难想到拓扑排序，但本题的图是可能存在环的，于是考虑可以使用 SCC 缩点，缩点后在 DAG 上跑一次拓扑排序 DP 即可。

此时定义 dp[c] 表示从起点 SCC 到达分量 $c$ 时最多取得的钱，沿拓扑序处理跨 SCC 边 $u\to v$ 时，用 dp[u] + scc_val[v] 更新 dp[v]，最后只在包含酒吧的 SCC 中取最大值。

注：构建 DAG 时没有去除平行边，不过因为每条平行边都同步增加并减少入度，因此不会破坏拓扑过程。若问题改成路径计数，重边会改变方案数，此时就必须去重。

Tarjan、建图与拓扑 DP 的总时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。

▶

P3627 抢掠计划

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];
vector<Edge> dag[maxn];

int dfn[maxn], low[maxn], timer;
int scc[maxn], scnt;
ll scc_val[maxn];

int stk[maxn], top;
bool ins[maxn];

ll val[maxn];
int bar[maxn];
bool vis[maxn];

int ind[maxn];
ll dp[maxn];

void tarjan( int u ) {
    dfn[u] = low[u] = ++ timer;
    stk[++ top] = u, ins[u] = true;

    for( auto [v, w] : adj[u] ) {
        if( !dfn[v] ) {
            tarjan( v );
            low[u] = min( low[u], low[v] );
        } else if( ins[v] ) {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( low[u] == dfn[u] ) {
        scnt ++; int v;
        do {
            v = stk[top --];
            ins[v] = 0;
            scc[v] = scnt;
            scc_val[scnt] += val[v];
        } while( v != u );
    }
}

void solve( ) {
    int n = read( ), m = read( );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back({ v, 0 });
    }

    for( int i = 1; i <= n; ++ i ) {
        val[i] = read( );
    }

    int S = read( ), P = read( );

    for( int i = 1; i <= P; ++ i ) {
        bar[i] = read( );
    }

    for( int i = 1; i <= n; ++ i ) {
        if( !dfn[i] ) tarjan( i );
    }

    for( int u = 1; u <= n; ++ u ) {
        for( auto [v, w] : adj[u] ) {
            if( scc[u] != scc[v] ) {
                dag[scc[u]].push_back({ scc[v], 0 });
                ind[scc[v]] ++;
            }
        }
    }
    
    for( int i = 1; i <= P; ++ i ) {
        vis[ scc[bar[i]] ] = 1;
    }

    for( int i = 1; i <= scnt; ++ i ) dp[i] = -inf;

    int st = scc[S];
    dp[st] = scc_val[st];

    queue<int> q;
    
    for( int i = 1; i <= scnt; ++ i ) {
        if( ind[i] == 0 ) q.push( i );
    }

    while( !q.empty( ) ) {
        int u = q.front( ); q.pop( );
        for( auto [v, w] : dag[u] ) {
            if( dp[u] != -inf ) {
                dp[v] = max( dp[v], dp[u] + scc_val[v] );
            }
            if( -- ind[v] == 0 ) q.push( v );
        }
    }

    ll ans = 0;
    for( int i = 1; i <= scnt; ++ i ) {
        if( vis[i] ) ans = max( ans, dp[i] );
    }
    cout << ans << '\n';
}

缩点后的问题就是带点权 DAG 上的最长路，不过只有从起点分量可达的状态才能参与转移。题目保证至少有一个酒吧可达，因此最终一定能在被标记的酒吧分量中取得有效答案。

记录

• 归属：SCC 缩点、拓扑排序；
• 新增：允许重复行走使 SCC 内点权可以一次性合并，缩点后再在 DAG 上从指定起点做带可达性标记的最长路。
• 分类：待定