[백준 4013] ATM

문제

https://www.acmicpc.net/problem/4013

 

알고리즘

SCC

 

풀이

여행 계획 세우기 문제와 거의 비슷합니다. 방문한 도시를 또 방문할 수 있다는 점에서 사이클이 존재함을 알 수 있고, 하나의 사이클안에 있는 ATM은 전부 얻을 수 있는 돈이므로 SCC를 통해 하나의 큰 정점으로 표현 가능합니다. DAG위에서 위상정렬 순서상 빠른 정점부터 얻을 수 있는 최대 금액을 갱신해나가면 됩니다. 이는 $SC$값을 역으로 순회하면 해결 가능합니다. 단, 위 문제와는 다른 점이 있다면 도착 정점이 여러 개라는 점입니다. 사용하는 변수가 많으므로 추가적인 변수들은 아래에 정리해두니, 코드를 보실 때 참고하시면 좋습니다.

 

$isres[i]$= $i$교차로에 레스토랑이 있을 때, True

$moneysum[i]$ = SCC의 $i$번째 정점에서 얻을 수 있는 금액

$sccadj[i]$ = SCC DAG 그래프의 인접 리스트

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M,u,v,S,P,x,VC,SC;

vector<vector<int>> adj,scc_adj;
vector<int> money,discovered,sccid,money_sum;
vector<bool> isres;
stack<int> st;

int cache[500000];

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);
    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        int ms = 0;
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            ms += money[t];
            if (t == here) break;
        }
        money_sum.emplace_back(ms);
        ++SC;
    }

    return ret;
}


int main() {
    FAST;
    cin >> N >> M;
    adj.resize(N);
    money.resize(N);
    isres.resize(N);

    rep(i, M) {
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
    }
    rep(i, N)
        cin >> money[i];
    cin >> S >> P;
    --S;
    rep(i, P) {
        cin >> x;
        --x;
        isres[x] = true;
    }

    discovered = sccid = vector<int>(N, -1);
    rep(i, N) if (discovered[i] == -1) scc(i);

    scc_adj.resize(SC);
    rep(here,N) for (auto there : adj[here]) {
        if (sccid[here] != sccid[there])
            scc_adj[sccid[here]].emplace_back(sccid[there]);
    }
    
    memset(cache, -0x3f, sizeof(cache));
    
    S = sccid[S];
    cache[S] = money_sum[S];
    
    for (int here = S;here >= 0;--here) {
        if (cache[here] < 0) continue;
        for (auto there : scc_adj[here])
            cache[there] = max(cache[there], cache[here] + money_sum[there]);
    }

    int ans = 0;
    rep(i, N) if(isres[i]) ans = max(ans, cache[sccid[i]]);
    cout << ans;
    return 0;
}