ปล้นตู้เอทีเอ็ม: กลุ่มที่วิ่งวนถึงกัน คือกองเงินกองเดียวที่ได้ครบเสมอ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> hd, nx, to_;                     // กราฟแบบรายการต่อกัน
vector<int> comp, low, num, stk, cash;

int main(){
    if(scanf("%d %d", &n, &m) != 2) return 0;
    hd.assign(n + 1, -1); nx.resize(m); to_.resize(m);
    for(int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); to_[i] = b; nx[i] = hd[a]; hd[a] = i; }
    cash.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) scanf("%d", &cash[i]);
    int s, p; scanf("%d %d", &s, &p);
    vector<char> pub(n + 1, 0);
    for(int i = 0; i < p; i++){ int x; scanf("%d", &x); pub[x] = 1; }

    // ทาร์ยานแบบวนลูป ไม่ใช้สแต็กของระบบ เพราะกราฟลึกได้ถึงห้าแสนชั้น
    comp.assign(n + 1, -1); low.assign(n + 1, 0); num.assign(n + 1, 0);
    vector<char> onstk(n + 1, 0);
    vector<int> it(n + 1, -1), callStk;
    int timer = 0, nc = 0;
    for(int s0 = 1; s0 <= n; s0++){
        if(num[s0]) continue;
        callStk.push_back(s0);
        num[s0] = low[s0] = ++timer; stk.push_back(s0); onstk[s0] = 1; it[s0] = hd[s0];
        while(!callStk.empty()){
            int u = callStk.back();
            if(it[u] != -1){
                int e = it[u]; it[u] = nx[e]; int v = to_[e];
                if(!num[v]){ num[v] = low[v] = ++timer; stk.push_back(v); onstk[v] = 1; it[v] = hd[v]; callStk.push_back(v); }
                else if(onstk[v]) low[u] = min(low[u], num[v]);
            } else {
                callStk.pop_back();
                if(!callStk.empty()) low[callStk.back()] = min(low[callStk.back()], low[u]);
                if(low[u] == num[u]){
                    while(true){ int w = stk.back(); stk.pop_back(); onstk[w] = 0; comp[w] = nc; if(w == u) break; }
                    nc++; }
            }
        }
    }

    // ยุบเป็นกราฟไร้วงจร แล้วหาทางที่ได้เงินมากสุด
    vector<ll> sum(nc, 0);
    for(int v = 1; v <= n; v++) sum[comp[v]] += cash[v];
    vector<char> hasPub(nc, 0);
    for(int v = 1; v <= n; v++) if(pub[v]) hasPub[comp[v]] = 1;
    // ลำดับที่ทาร์ยานปิดองค์ประกอบ เป็นลำดับทอพอโลยีกลับหัวอยู่แล้ว
    vector<int> ord(nc); for(int i = 0; i < nc; i++) ord[i] = nc - 1 - i;
    vector<ll> dp(nc, -1); dp[comp[s]] = sum[comp[s]];
    vector<vector<int>> adj(nc);
    for(int u = 1; u <= n; u++) for(int e = hd[u]; e != -1; e = nx[e]){
        int v = to_[e]; if(comp[u] != comp[v]) adj[comp[u]].push_back(comp[v]); }
    for(int idx = 0; idx < nc; idx++){
        int c = ord[idx]; if(dp[c] < 0) continue;
        for(int d : adj[c]) if(dp[c] + sum[d] > dp[d]) dp[d] = dp[c] + sum[d];
    }
    ll ans = 0;
    for(int c = 0; c < nc; c++) if(hasPub[c] && dp[c] > ans) ans = dp[c];
    printf("%lld\n", ans);
}

// ตัวตรวจ ค้นทุกสถานะ (จุดที่ยืน, เซตของตู้ที่ปล้นแล้ว)
// ไม่มีคำว่าองค์ประกอบเชื่อมโยงเข้มอยู่ในนี้เลย ใช้ได้เฉพาะกราฟจิ๋ว
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; scanf("%d %d", &n, &m);
    vector<vector<int>> g(n);
    for(int i = 0; i < m; i++){ int a, b; scanf("%d %d", &a, &b); g[a-1].push_back(b-1); }
    vector<int> w(n); for(auto &x : w) scanf("%d", &x);
    int s, p; scanf("%d %d", &s, &p); s--;
    vector<int> pub(n, 0); for(int i = 0; i < p; i++){ int x; scanf("%d", &x); pub[x-1] = 1; }
    vector<vector<int>> best(n, vector<int>(1 << n, -1));
    deque<pair<int,int>> q; int st = 1 << s; best[s][st] = w[s]; q.push_back({s, st});
    while(!q.empty()){
        auto [u, mask] = q.front(); q.pop_front(); int cur = best[u][mask];
        for(int v : g[u]){
            int nm = mask | (1 << v);
            int nv = cur + ((mask >> v & 1) ? 0 : w[v]);
            if(nv > best[v][nm]){ best[v][nm] = nv; q.push_back({v, nm}); } }
    }
    int ans = -1;
    for(int u = 0; u < n; u++) if(pub[u]) for(int mk = 0; mk < (1 << n); mk++) ans = max(ans, best[u][mk]);
    printf("%d\n", ans);
}