fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int INF = 1e9;
  5. int n, m, timee , scc = 0, res = -1;
  6. int low[200001], num[200001], dele[200001], longchim[200001];
  7. vector<int> p[200001];
  8. vector<int> newl[200001];
  9. stack<int> st;
  10. int c[200001], dp[200001];
  11. void nhap() {
  12.     memset(dp, -1, sizeof(dp));
  13.     cin >> n >> m;
  14.     for (int i = 1; i <= n; i++) {
  15.         cin >> c[i];
  16.     }
  17.     for (int i = 1; i <= m; i++) {
  18.         int a, b;
  19.         cin >> a >> b;
  20.         p[a].push_back(b);
  21.     }
  22. }
  23. void cc(int u) {
  24.     low[u] = num[u] = ++timee;
  25.     st.push(u);
  26.     for (int v : p[u]) {
  27.         if (dele[v]) continue;
  28.         if (!num[v]) {
  29.             cc(v);
  30.             low[u] = min(low[u], low[v]);
  31.         }
  32.         else low[u] = min(low[u], num[v]);
  33.     }
  34.     if (low[u] == num[u]) {
  35.         scc++;
  36.         int sum = 0;
  37.         while (true) {
  38.             int l = st.top();
  39.             st.pop();
  40.             sum += c[l];
  41.             dele[l] = scc;
  42.             if (l == u) break;
  43.         }
  44.         longchim[scc] = sum;
  45.     }
  46. }
  47. int dfs(int u) {
  48.     if (dp[u] != -1) return dp[u];
  49.     dp[u] = longchim[u];
  50.     for (int v : newl[u]) {
  51.         dfs(v);
  52.         dp[u] = max(dp[u], dp[v] + longchim[u]);
  53.     }
  54.     return dp[u];
  55. }
  56. signed main() {
  57.     nhap();
  58.     for (int i = 1; i <= n; i++) {
  59.         if (!num[i]) cc(i);
  60.     }
  61.     for (int i = 1; i <= n; i++) {
  62.         for (int v : p[i]) {
  63.             if (dele[v] != dele[i]) newl[dele[i]].push_back(dele[v]);
  64.         }
  65.     }
  66.     for (int i = 1; i <= scc; i++) {
  67.         res = max(res, dfs(i));
  68.     }
  69.     cout << res;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 18216KB
comments (?)
stdin
copy 
4 4
4 5 2 7
1 2
2 1
1 3
2 4
stdout
copy 
16
https://ideone.com/gl260V
language:
C++14 (clang 8.0)
created:
272 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!