本文共 3632 字，大约阅读时间需要 12 分钟。

2840 ATM

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了。

例如，假设该城中有 6 个路口。市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢 劫的现金总数为 47，实施的抢劫路线是：1-2-4-1-2-3-5。

输入

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。

接下来M行，每行两个整数，这两个整数都在1到N之间， 第i+1行的两个整数表示第i条道路的起点和终点的路口编号。 接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。 接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。 接下来的一行中有P个整数，表示P个有酒吧的路口的编号 N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。 输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

输出

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

数据范围

20% 2 <= N <= 200 2 <= M <= 300

60% 2 <= N <= 3000 2 <= M <= 3000 100% 2 <= N <= 500000 2 <= M <= 500000

输入样例1:

6 7

1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6

输入样例2:

6 7

1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 2 3 4

输入样例3:

6 7

1 2 2 3 3 5 2 4 4 1 2 6 6 5 100 12 18 76 1 5 1 4 4 2 3 4

输出样例1:

47

输出样例2:

46

输出样例3:

206

思想

先缩点，然后重建图，最后一个深搜取最佳答案。

代码实现

#include 
   
    using namespace std;#define maxn 500010int n, m;int cnt;// 记录强连通分量的个数int vis_num;// 遍历的步数int dfn[maxn];// 记录元素第一次被访问的步数int low[maxn];// 包含i的强连通分量最早被访问的步数int indegree[maxn];// i从属的强连通分量，不同的强连通分量值不同，缩点使用stack
    
      s;int val[maxn];// 第i个位置的钱数int st;// 起点int bar_num;// 酒吧数量int bar[maxn];// 酒吧位置int cost[maxn], ok[maxn], dp[maxn];// 存边vector
     
       mp[maxn], mp1[maxn];// 记录强连通分量里的点及个数vector
      
        strongly_connected[maxn];void tarjan(int u) {
       int v;    dfn[u] = low[u] = ++vis_num;    // 入栈    s.push(u);    for (int i = 0; i < mp[u].size(); i++) {
           // 下一个访问的点        v = mp[u][i];        if (!dfn[v]) {
               tarjan(v);            // 判断u是否为v的子节点            low[u] = min(low[u], low[v]);        } else if (!indegree[v]) {
               low[u] = min(low[u], dfn[v]);        }    }    // u为强连通分量的根    if (dfn[u] == low[u]) {
           // 强连通分量的个数+1        cnt++;        // 退栈        while (1) {
               // v 该强连通分量成员            v = s.top();            s.pop();            indegree[v] = cnt;            strongly_connected[cnt].push_back(v);            if (u == v) {
                   break;            }        }    }}void dfs(int u) {
       if (dp[u] != -1) {
           return;    }    int ans = cost[u];    for (int i = 0; i < mp1[u].size(); i++) {
           int v = mp1[u][i];        dfs(v);        if (ok[v]) {
               ans = max(ans, dp[v] + cost[u]);            ok[u] = 1;        }    }    dp[u] = ans;}int main() {
       int u, v;    cin >> n >> m;    for (int i = 1; i <= m; i++) {
           cin >> u >> v;        mp[u].push_back(v);    }    for (int i = 1; i <= n; i++) {
           cin >> val[i];    }    cin >> st >> bar_num;    for (int i = 1; i <= bar_num; i++) {
           int use;        cin >> use;        bar[use] = 1;    }    tarjan(st);    // 计算强连通花销    for (int i = 1; i <= cnt; i++) {
           for (int j = 0; j < strongly_connected[i].size(); j++) {
               u = strongly_connected[i][j];            cost[i] += val[u];            if (bar[u]) {
                   ok[i] = 1;            }        }    }    // 重建图    for (int i = 1; i <= n; i++) {
           for (int j = 0; j < mp[i].size(); j++) {
               v = mp[i][j];            if (indegree[v] != indegree[i]) {
                   mp1[indegree[i]].push_back(indegree[v]);            }        }    }    memset(dp, -1, sizeof(dp));    dfs(indegree[st]);    printf("%d\n", dp[indegree[st]]);    return 0;}
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/112075036 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！