BOJ 4013 ATM

1 개요

BOJ 4013 ATM

• 백준 온라인 저지 4013번 문제
• BOJ 44단계

2 C++

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

int N, M, S, P, cnt;
vector<vector<int>> adj, scc, sccAdj;
vector<int> cash, sccCash, restaurant, dfsNum, sccIndex, indegree, dp;
vector<bool> finished;
stack<int> s;

int dfs(int cur) {
    dfsNum[cur] = ++cnt;
    s.push(cur);
    int ret = dfsNum[cur];
    for (int next : adj[cur]) {
        if (dfsNum[next] == 0) {
            ret = min(ret, dfs(next));
        } else if (!finished[next]) {
            ret = min(ret, dfsNum[next]);
        }
    }
    if (ret == dfsNum[cur]) {
        vector<int> cc;
        int curIndex = scc.size();
        while (true) {
            int val = s.top();
            s.pop();
            finished[val] = true;
            cc.push_back(val);
            sccIndex[val] = curIndex;
            if (val == cur) break;
        }
        scc.push_back(cc);
    }
    return ret;
}

void createSCCs() {
    dfsNum.resize(N + 1);
    finished.resize(N + 1);
    sccIndex.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        if (dfsNum[i] == 0) dfs(i);
    }
    indegree.resize(scc.size());
    sccAdj.resize(scc.size());
    for (int cur = 1; cur <= N; ++cur) 
        for (int to : adj[cur]) 
            if (sccIndex[cur] != sccIndex[to]) {
                sccAdj[sccIndex[cur]].push_back(sccIndex[to]);
                ++indegree[sccIndex[to]];
            }
}

void topologySort() {
    queue<int> q;
    for (int i = 0; i < scc.size(); ++i) {
        if (indegree[i] == 0) q.push(i);
    }
    dp.resize(scc.size());
    sccCash.resize(scc.size());
    for (int i = 1; i <= N; ++i) {
        sccCash[sccIndex[i]] += cash[i];
    }
    dp[sccIndex[S]] = sccCash[sccIndex[S]];
    bool flag = false;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == sccIndex[S]) flag = true;
        for (int next : sccAdj[cur]) {
            if(flag) dp[next] = max(dp[next], dp[cur] + sccCash[next]);
            indegree[next]--;
            if (indegree[next] == 0) q.push(next);
        }
    }
}

void solve() {
    createSCCs();
    topologySort();
    int answer = 0;
    for (int i = 0; i < P; ++i) {
        answer = max(answer, dp[sccIndex[restaurant[i]]]);
    }
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    adj.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        int from, to;
        cin >> from >> to;
        adj[from].push_back(to);
    }
    cash.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> cash[i];
    }
    cin >> S >> P;
    restaurant.resize(P);
    for (int i = 0; i < P; ++i) {
        cin >> restaurant[i];
    }
    solve();
}