Hiểu bài toán

Bài toán yêu cầu tìm số tiền tối đa mà Banditji có thể đánh cắp khi bắt đầu từ một nút S, đi qua các nút trong đồ thị có hướng (có thể đi lại nhiều lần), chỉ lấy tiền ở lần đầu tiên đến một nút, và phải kết thúc tại một trong các nút là quán bar. Đồ thị có đến 500,000 nút và cạnh. Số tiền tại mỗi nút không quá 4000.

Vấn đề cốt lõi là nhận ra rằng Banditji có thể đi lại tự do trong các thành phần liên thông mạnh (SCC) mà anh ta có thể vào được. Nếu một nút nằm trong một chu trình hoặc có thể đi đến một nút khác và quay lại, thì Banditji có thể lấy tiền của tất cả các nút trong SCC đó. Do đó, ta có thể thu gọn đồ thị thành đồ thị DAG các SCC (Strongly Connected Components). Sau đó, bài toán trở thành tìm đường đi có tổng trọng số (tiền) lớn nhất từ SCC chứa S đến bất kỳ SCC nào chứa ít nhất một quán bar, trên đồ thị DAG.

Đặc biệt, do Banditji có thể đi qua một nút nhiều lần, anh ta có thể đi qua một SCC, sau đó đi đến một quán bar, nhưng nếu từ quán bar đó có đường đi đến một SCC khác mà anh ta chưa thăm, anh ta có thể quay lại SCC ban đầu và đi đến SCC kia (vì đồ thị là DAG, việc này phụ thuộc vào thứ tự topo). Tuy nhiên, ràng buộc 'kết thúc tại quán bar' có nghĩa là anh ta phải chọn một điểm dừng cuối cùng. Nếu anh ta có thể đến một SCC có quán bar và SCC đó có thể đi đến một SCC khác, anh ta không thể quay lại SCC ban đầu nếu chỉ đi theo chiều đồ thị. Nhưng do có thể đi qua nút nhiều lần và chu trình, anh ta có thể thu thập tiền ở tất cả các SCC có thểReachable từ S và có đường về SCC đó hoặc có thể đi đến quán bar ở cuối. Tuy nhiên, lời giải chi tiết cho thấy bài toán này thực chất là tìm 'tổng trọng số lớn nhất của các node có thểReachable từ S và có thểReachable đến một quán bar'. Vì Banditji có thể đi lòng vòng, anh ta có thể thu thập tiền ở bất kỳ nút nào nằm trên một chu trình có thể đi tới quán bar, hoặc nằm trên đường đi tới quán bar.

Cụ thể hơn, lời giải hoạt động như sau:

1. Tìm SCCs và thu gọn đồ thị thành DAG.
2. Gán trọng số cho mỗi SCC là tổng tiền của các nút trong SCC đó.
3. Đánh dấu các SCC chứa quán bar.
4. Tìm các SCC 'cần thiết': các SCC nằm trên đường đi từ SCC chứa S đến một SCC chứa quán bar. Các SCC không thuộc đường đi này sẽ không thể lấy tiền.
5. Tính tổng tiền của các SCC cần thiết.

Lưu ý về việc đi lại: Do Banditji có thể đi qua nút nhiều lần, anh ta có thể vào một SCC, lấy tiền, đi ra, và nếu có đường quay lại SCC đó (tạo chu trình), anh ta có thể lấy tiền ở các SCC khác nữa. Tuy nhiên, với ràng buộc 'kết thúc tại quán bar', anh ta chỉ có thể lấy tiền ở các SCC mà từ đó có đường đến một quán bar. Nhưng do có thể đi lòng vòng, anh ta có thể tối ưu hóa bằng cách lấy tiền ở các SCC trên một chu trình lớn.

Giải pháp accepted từ TuanAnhTank và haidang3004 sử dụng Tarjan để tìm SCC, sau đó tạo đồ thị DAG, rồi dùng DFS/BFS hoặc Topo Sort để tìm các nút có thểReachable từ S (điều kiện 1) và có thểReachable đến một quán bar (điều kiện 2). Nút nào thỏa mãn cả hai điều kiện thì cộng dồn tiền.

Các cách tiếp cận

Cách SCC + DAG + Reachability Analysis

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
int n, m, s, p;
int money[N];
vector<int> adj[N], rev_adj[N];
vector<int> dag_adj[N];
bool is_bar[N];

// Tarjan SCC
int num[N], low[N], timer;
int scc_id[N], scc_cnt;
long long scc_sum[N];
bool scc_has_bar[N];
stack<int> st;
bool in_stack[N];

void tarjan(int u) {
    num[u] = low[u] = ++timer;
    st.push(u);
    in_stack[u] = true;
    for (int v : adj[u]) {
        if (num[v]) {
            if (in_stack[v]) low[u] = min(low[u], num[v]);
        } else {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] == num[u]) {
        scc_cnt++;
        while (true) {
            int v = st.top(); st.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            scc_sum[scc_cnt] += money[v];
            if (is_bar[v]) scc_has_bar[scc_cnt] = true;
            if (v == u) break;
        }
    }
}

// DFS trên DAG
double dag_reach[N]; // 0: chưa thăm, 1: từ S đến được, 2: đến được bar
void dfs_forward(int u) {
    dag_reach[u] = 1;
    for (int v : dag_adj[u]) {
        if (dag_reach[v] != 1) dfs_forward(v);
    }
}

bool visited_rev[N];
void dfs_backward(int u) {
    visited_rev[u] = true;
    for (int v : dag_adj[u]) {
        if (!visited_rev[v]) dfs_backward(v);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (fopen("atm.inp", "r")) freopen("atm.inp", "r", stdin);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) cin >> money[i];
    cin >> s >> p;
    for (int i = 0; i < p; i++) {
        int x; cin >> x;
        is_bar[x] = true;
    }

    // 1. Find SCCs
    for (int i = 1; i <= n; i++) {
        if (!num[i]) tarjan(i);
    }

    // 2. Build DAG
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                dag_adj[scc_id[u]].push_back(scc_id[v]);
            }
        }
    }

    // 3. Find SCCs reachable from S's SCC
    int start_scc = scc_id[s];
    dfs_forward(start_scc);

    // 4. Find SCCs that can reach a Bar SCC
    // We need to reverse the DAG for this
    vector<int> rev_dag_adj[N];
    for (int u = 1; u <= scc_cnt; u++) {
        for (int v : dag_adj[u]) {
            rev_dag_adj[v].push_back(u);
        }
    }

    // Start DFS from all SCCs that have bars
    queue<int> q;
    vector<bool> can_reach_bar(scc_cnt + 1, false);
    for (int i = 1; i <= scc_cnt; i++) {
        if (scc_has_bar[i]) {
            can_reach_bar[i] = true;
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : rev_dag_adj[u]) {
            if (!can_reach_bar[v]) {
                can_reach_bar[v] = true;
                q.push(v);
            }
        }
    }

    // 5. Sum up
    long long ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (dag_reach[i] == 1 && can_reach_bar[i]) {
            ans += scc_sum[i];
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

1. SCC Decomposition: Sử dụng thuật toán Tarjan để tìm các SCCs. Điều này cho phép ta coi mỗi SCC là một 'supernode' trong đồ thị DAG.
2. Xây dựng DAG: Tạo đồ thị mới giữa các SCCs.
3. Tìm nút có thể đi tới từ S: Chạy DFS/BFS từ SCC chứa S trên DAG để đánh dấu các SCC có thểReachable.
4. Tìm nút có thể đi tới quán bar: Chạy DFS/BFS ngược (trên đồ thị DAG đảo chiều) từ các SCC chứa quán bar. Các SCC được đánh dấu là có thể đi tới quán bar.
5. Tính tổng: Chỉ cộng dồn tiền của các SCC vừa có thểReachable từ S, vừa có thểReachable đến quán bar.

Lưu ý: Do Banditji có thể đi lòng vòng trong SCC và qua lại giữa các SCC (nếu có chu trình), anh ta thực sự có thể lấy tiền ở bất kỳ SCC nào nằm trên một chu trình có thể đi đến quán bar. Tuy nhiên, với ràng buộc 'phải kết thúc tại quán bar', cách tiếp cận này là chính xác: anh ta có thể đi đến SCC đó, lấy tiền, sau đó đi đến quán bar và dừng lại. Nếu anh ta có thể đi từ SCC A -> SCC B -> Quán bar, anh ta có thể lấy tiền ở cả A và B.

Cách Simplified Reachability (Bỏ qua logic đi lòng vòng)

// Tương tự Approach 1, nhưng logic được rút gọn trong phần giải thích
// Code structure giữ nguyên, chỉ khác biệt ở bước suy luận

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Cách tiếp cận này về cơ bản là giống Approach 1 nhưng nhấn mạnh vào việc tại sao nó hoạt động.

Banditji có thể di chuyển tự do giữa các SCC nếu có đường đi (vì có thể đi lại nhiều lần, và nếu có chu trình, anh ta có thể vào SCC đó). Tuy nhiên, anh ta chỉ có thể lấy tiền một lần.

Vấn đề nan giải: Nếu anh ta đi S -> A -> B -> Bar, nhưng có đường từ Bar -> A, anh ta có thể lấy tiền ở A, đến Bar, sau đó quay lại A và lấy tiền ở B? Không, vì Bar là nơi kết thúc.

Tuy nhiên, có một trường hợp đặc biệt: Nếu có chu trình A -> B -> A, và có đường từ A -> Bar. Anh ta có thể vào A, lấy tiền, đi B, lấy tiền, quay lại A, rồi đi Bar.

Giải pháp SCC + DAG xử lý điều này bằng cách coi A và B là một khối (nếu chúng nằm trong SCC). Nếu chúng nằm trong các SCC khác nhau nhưng có chu trình (A -> B -> A), thì chúng phải nằm trong cùng một SCC (định nghĩa SCC là maximal strongly connected subgraph). Vì vậy, Tarjan sẽ gom chúng vào một SCC.

Vậy, bài toán thực sự là: Tìm tập hợp các SCC mà:

1. Có đường từ SCC[S] đến SCC đó.
2. Có đường từ SCC đó đến một SCC chứa Bar.

Đây là cách chính xác nhất để giải quyết bài toán này.

Cách Brute Force (Không khả thi)

// Pseudocode for Brute Force
// DFS(state)
//   if (state is bar) update max
//   for next in adj[state]:
//     if not visited[next]:
//        visited[next] = true; money_acc += money[next];
//        DFS(next);
//        visited[next] = false; // Backtracking

// Complexity: O(2^N) or O(N!)

• Time Complexity: Exponential
• Space Complexity: O(N)

Thử tất cả các đường đi có thể từ S đến bar, không đi qua node đã lấy tiền. Với N lên tới 500,000, cách này hoàn toàn không chạy được.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giảm quy mô bằng cách gom các nút trong chu trình (SCC) thành một nút duy nhất với trọng số là tổng tiền của các nút trong chu trình.
• Sau khi thu gọn đồ thị thành DAG, bài toán trở thành bài toán tìm tập hợp các nút nằm trên đường đi từ source đến sink (nút có bar).
• Banditji có thể đi lòng vòng để lấy tiền ở tất cả các nút trong SCC, và có thể đi qua các SCC khác nếu có đường đi. Do đó, chỉ cần kiểm tra tính Reachability là đủ.

Lỗi thường gặp

• Quên处理 việc một node có thể thuộc nhiều SCC nếu graph không liên thông mạnh. Phải dùng Tarjan (hoặc Kosaraju).
• Sai lầm khi suy nghĩ về việc 'đi lòng vòng': Nếu không dùng SCC, ta có thể nghĩ rằng không thể lấy tiền ở B nếu đi qua A, Bar, rồi quay lại A để vào B (vì Bar là kết thúc). Tuy nhiên, nếu A và B có chu trình, chúng thuộc cùng một SCC và tiền được tính gộp. Nếu chúng thuộc SCC khác nhau nhưng có chu trình A->B->A, chúng vẫn thuộc cùng một SCC. Do đó, Tarjan là bắt buộc.
• Xử lý đồ thị lớn: Phải dùng Adjacency List và cẩn thận với stack overflow (dùng iterative DFS hoặc tăng stack size).