抢掠计划

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2604 字
Tarjan缩点后DAG上最大点权路径
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1518
// 题意：单向道路图上从 S 出发、在任一酒吧结束，每个路口的 ATM 只能抢一次，求最多能抢到的现金总额。
// 思路：Tarjan 缩点，每个分量的点权是分量内 ATM 金额之和，再在缩点 DAG 上按拓扑序做最长路 DP，取所有酒吧分量的最大值。
// 1. 分量内可以反复走并抢光所有 ATM，所以必须先把点权合并到分量上再 DP。
// 2. Tarjan 分量编号是逆拓扑序，按编号从大到小递推正好是拓扑序，不需要再跑一遍拓扑排序。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：DP 只能从 S 所在分量出发沿边正向传播，不能对所有分量取最大值，否则会把到不了的分支算进去。
// 易错点：答案只看有酒吧的分量，终点必须是酒吧，不能取全图最大 DP 值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int MAXM = 500005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], scnt;
bool instk[MAXN];
int head2[MAXN], to2[MAXM], nxt2[MAXM], ecnt2;
int money[MAXN];
long long val[MAXN];
long long dp[MAXN];
bool bar[MAXN];
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            val[scnt] += money[x];
            if(x == u) break;
        }
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for(int i = 1; i <= n; i++){
        cin >> money[i];
    }
    int s, p;
    cin >> s >> p;
    for(int i = 0; i < p; i++){
        int x;
        cin >> x;
        bar[x] = true;
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(int j = head[u]; j; j = nxt[j]){
            int v = to[j];
            if(scc[u] != scc[v]){
                to2[++ecnt2] = scc[v];
                nxt2[ecnt2] = head2[scc[u]];
                head2[scc[u]] = ecnt2;
            }
        }
    }
    int start = scc[s];
    for(int i = 1; i <= scnt; i++){
        dp[i] = -1;
    }
    dp[start] = val[start];
    for(int i = scnt; i >= 1; i--){
        if(dp[i] < 0) continue;
        for(int j = head2[i]; j; j = nxt2[j]){
            int c = to2[j];
            if(dp[c] < dp[i] + val[c]) dp[c] = dp[i] + val[c];
        }
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        if(bar[i] && dp[scc[i]] > ans) ans = dp[scc[i]];
    }
    cout << ans << "\n";
    return 0;
}
抢掠计划

正文

一本通·提高篇的其它内容
