题面

大秦为你打开题目传送门

题目描述

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 机中的钱数 $a_i$。

接下来一行包含两个整数 $S,P$，$S$ 表示市中心的编号，也就是出发的路口。$P$ 表示酒吧数目。

接下来的一行中有 $P$ 个整数，表示 $P$ 个有酒吧的路口的编号。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

样例输出 #1

1
47

提示

对于 $50\%$ 的数据，保证 $N, M \le 3000$。

对于 $100\%$ 的数据，保证 $N, M \le 5\times 10^5$，$0 \le a_i \le 4000$。保证可以从市中心沿着 Siruseri 的单向的道路到达其中的至少一个酒吧。

思路

这道题目很简单，由于在一个强连通分量的点互相可达，题目没有说不可以走重复的点，也就是说：一个强连通分量的点都是可以取到的，且如果这个强连通分量中有酒吧，这个强连通分量就可以看成一个酒吧。

那么就直接 Tarjan 缩点，把每一个强连通分量都看成一个超级点，跑最长路即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 5e5 + 10;
const int M = 5e5 + 10;

class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m, s, p;
Graph G;
int uid[N], vid[N];
ll g[N];
int r[N];

inline void Input() {
    read(n, m);
    int u, v;
    for(int i = 1; i <= m; i++) {
        read(uid[i], vid[i]);
        G.AddEdge(uid[i], vid[i]);
    }
    for(int i = 1; i <= n; i++) {
        read(g[i]);
    }
    read(s, p);
    for(int i = 1; i <= p; i++) {
        read(r[i]);
    }
}

int dfn[N], low[N], cntd;
int cl[N], cntc;
int stk[N], top, instk[N];

ll sum[N];

inline void Tarjan(int u) {
    low[u] = dfn[u] = ++cntd;
    stk[++top] = u;
    instk[u] = 1;
    for(int i = G.head(u); i ; i = G.nt(i)) {
        int v = G.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]) {
        cntc++;
        instk[u] = 0;
        cl[u] = cntc;
        sum[cntc] += g[u];
        while(stk[top] != u) {
            instk[stk[top]] = 0;
            cl[stk[top]] = cntc;
            sum[cntc] += g[stk[top]];
            top--;
        }
        top--;
    }
}

Graph DAG;
ll dis[N];
int vis[N];

inline void Dijkstra(int st) {
    priority_queue<pair<ll , ll > > q;
    dis[st] = sum[st];
    q.push(make_pair(dis[st], st));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = DAG.head(u); i ; i = DAG.nt(i)) {
            int v = DAG.to(i);
            if(dis[u] + sum[v] > dis[v]) {
                dis[v] = dis[u] + sum[v];
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            Tarjan(i);
        }
    }
    set<pair<int , int > >st;
    for(int i = 1; i <= m; i++) {
        if(cl[uid[i]] != cl[vid[i]]) {
            st.insert(make_pair(cl[uid[i]], cl[vid[i]]));
        }
    }
    for(auto &p : st) {
        DAG.AddEdge(p.first, p.second);
    }
    Dijkstra(cl[s]);
    ll ans = 0;
    for(int i = 1; i <= p; i++) {
        ans = max(ans, dis[cl[r[i]]]);
    }
    printf("%lld", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}