Good Travels｜缩点模版 · znzryb

## 思路讲解

![image](https://media.znzryb.com/20260109-4c604326/image_ae664ee6.png)

## AC代码

AC
[https://www.spoj.com/status/ns=35103793](https://www.spoj.com/status/ns=35103793)



::: 源代码

```cpp
// by Gospel_rock
// title: Good Travels scc
// timeLimit: 1000
// url: https://vjudge.net/problem/SPOJ-GOODA#author=GPT_zh
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT, S, E;

void Solve() {
    cin >> N >> M >> S >> E;
    vector<ll> A(N + 4);
    FOR(i, 1, N) { cin >> A[i]; }
    vector<vector<ll>> g(N + 5);
    FOR(i, 1, M) {
        ll u, v;
        cin >> u >> v;
        g[u].PB(v);
    }
    vector<ll> tin(N + 5), low(N + 5);
    vector<ll> stk;
    vector<char> instk(N + 5);
    vector<ll> scc(N + 5);
    vector<ll> scca(N+5);
    ll idx = 0, sccidx = 0;
    auto dfs1 = [&](auto self, ll u) -> void {
        tin[u] = low[u] = ++idx;
        stk.PB(u);
        instk[u] = 1;
        for (auto v : g[u]) {
            if (!tin[v]) {
                self(self, v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], low[v]);
            }
        }
        if (tin[u] == low[u]) { // u是 scc 的根
            ++sccidx;
            ll y=0;
            do {
                y = stk.back();
                stk.pop_back();
                instk[y] = 0;
                scc[y] = sccidx;
                scca[sccidx]+=A[y];
            } while (y != u);
        }
    };
    FOR(i,1,N){
        if(!tin[i]){
            dfs1(dfs1,i);
        }
    }
    vector<vector<ll> > scg(sccidx+5);
    vector<ll> dp(sccidx+5,-INF);
    vector<ll> in(sccidx+5);
    FOR(u,1,N){
        for(auto v:g[u]){
            if(scc[u]==scc[v]) continue;
            scg[scc[u]].PB(scc[v]);
            in[scc[v]]++;
        }
    }
    // exit(0);
    queue<ll> q;
    FOR(i,1,sccidx){
        if(in[i]==0){
            q.push(i);
        }
    }
    dp[scc[S]]=scca[scc[S]];
    while(!q.empty()){
        auto u=q.front();q.pop();
        for(auto v:scg[u]){
            dp[v]=max(dp[v],dp[u]+scca[v]);
            in[v]--;
            if(in[v]==0){
                q.push(v);
            }
        }
    }
    ll ans=0;
    // FOR(i,1,sccidx){
    //     ans=max(dp[i],ans);
    // }
    cout<<(ll)dp[scc[E]]<<"\n";


// #ifdef LOCAL
//     debug(sccidx);
//     cerr<<"scc:";
//     FOR(i,1,N){
//         cerr<<scc[i]<<" ";
//     }
//     cerr<<"\n";
//     cerr<<"scca:";
//     FOR(i,1,sccidx){
//         cerr<<scca[i]<<" ";
//     }
//     cerr<<"\n";
//     FOR(i,1,sccidx){
//         cerr<<i<<":";
//         FOR(j,0,SZ(scg[i])-1){
//             cerr<<scg[i][j]<<" ";
//         }
//         cerr<<"\n";
//     }
//     cerr<<"dp:";
//     FOR(i,1,sccidx){
//         cerr<<dp[i]<<" ";
//     }
//     cerr<<"\n";
// #endif
   
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // cin >> lT;
    // while (lT--)
        Solve();
    return 0;
}
/*
AC
https://www.spoj.com/status/ns=35103793

*/
```


:::


## 心路历程（WA，TLE，MLE……）