P3387

我的做法就是将原图缩点，得到一个DAG新图，在新图上进行DP求最长路径。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5 + 10;
 4 int n, m, t;
 5 int dfn[N], low[N], a[N];
 6 int tot, head[N], to[N], nxt[N];
 7 void add(int x, int y) {
 8     nxt[++ tot] = head[x]; head[x] = tot, to[tot] = y;
 9 }
10 int st[N], top, bel[N], vis[N];
11 int idx, num[N], cnt[N];
12 void tarjan(int x) {
13     dfn[x] = low[x] = ++ t;
14     st[++ top] = x, vis[x] = 1;
15     for (int i = head[x]; i; i = nxt[i]) {
16         int y = to[i];
17         if (!dfn[y]) {
18             tarjan(y);
19             low[x] = min(low[x], low[y]);
20         }
21         else if (vis[y]) 
22             low[x] = min(low[x], dfn[y]);
23     }
24     if(low[x] == dfn[x]) {
25         idx ++;
26         int v;
27         do {
28             v = st[top --];
29             cnt[idx] ++;
30             num[idx] += a[v];
31             bel[v] = idx;
32             vis[v] = 0;    
33         } while (v != x);
34     }
35 }
36 vector<int> e[N];
37 int dp[N];
38 void dfs(int u, int fa) {
39     if (vis[u]) return ;
40     vis[u] = 1;
41     dp[u] = num[u];
42     for (int i = 0; i < e[u].size(); i ++) {
43         int v = e[u][i];
44         if (v == fa) continue;
45         dfs(v, u);
46         dp[u] = max(dp[u], num[u] + dp[v]);
47     }
48 }
49 int main() {
50     scanf("%d %d", &n, &m);
51     for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
52     for (int i = 1; i <= m; i ++) {
53         int u, v; scanf("%d %d", &u, &v);
54         add(u, v);
55     }    
56     for (int i = 1; i <= n; i ++) 
57         if (!dfn[i]) tarjan(i);
58     for (int i = 1; i <= n; i ++) {
59         for (int j = head[i]; j; j = nxt[j]) {
60             int v = to[j];
61             if (bel[i] != bel[v]) e[bel[i]].push_back(bel[v]);
62         }
63     }
64     memset(vis, 0, sizeof vis);
65     for (int i = 1; i <= idx; i ++) {
66         if (!vis[i]) dfs(i, 0);
67     }
68     int ans = 0;
69     for (int i = 1; i <= idx; i ++) ans = max(ans, dp[i]);
70     printf("%d\n", ans);
71     return 0;
72 }