[백준 4013] ATM C++

4013번: ATM

강한 연결 요소, 다이나믹 프로그래밍

---

처음 풀어보는 플레2 문제였다. 풀려서 기분이 매우 좋았음

우선 모든 정점들을 dfs로 순회하며 각 정점의 SCC를 구해줬다.

SCC를 구하면서 해당 SCC에 속하는 현금의 양 + 해당 SCC에 레스토랑이 있는지 판단해 주었다.

 

구한 SCC를 통해서 SCC 그래프를 만들어 주었다. -> make_sccgraph()

 

이제 DP문제로 바뀌게 되었다.

 

시작점의 SCC에서 출발해, 레스토랑이 있는 SCC까지의 거리의 최댓값을 구하면 된다.

top-down 방식을 사용해서 풀었고, 유의할 점은 도달한 SCC가 리프 노드이면서 레스토랑이 아닌경우에는 도착점이 될 수 없기 때문에 0을 반환하도록 했다.

레스토랑이 아닌 경우에 0을 반환해야 하는데 !를 안붙여줘서 여러번 틀렸다.

 

만약 레스토랑에 도달할 수 없는 경우가 있다면 조금 더 복잡해졌을 것 같고, 단순 1차원 배열의 dp가 아니라 레스토랑에 도착하는데 벽이 있고 벽을 부술 수 있는 등의 문제를 만들어서 dp 배열의 차원이 높아졌다면 더 어려웠을 것 같다

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 500001
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, S, P;
bool is_rest[MAX];
bool is_sccrest[MAX];
int discovered[MAX];
int sccnum[MAX];
 
ll sccmoney[MAX];
ll money[MAX];
ll sccmaxmoney[MAX];
 
vector<ll> adj[MAX];
vector<int> sccgraph[MAX];
vector<int> stk;
 
int sccCounter, vertaxCounter;
 
void input(){
    cin >> N >> M;
    int u, v;
    for(int i = 0; i < M; i++){
        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++){
        cin >> u;
        is_rest[u] = true;
    }
    
    memset(discovered, -1, sizeof(discovered));
    memset(sccnum, -1, sizeof(sccnum));
    memset(sccmaxmoney, -1, sizeof(sccmaxmoney));
}
 
int SCC(int now){
    int ret = discovered[now] = vertaxCounter++;
    stk.push_back(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(discovered[next] == -1){
            ret = min(ret, SCC(next));
        }
        else if(sccnum[next] == -1){
            ret = min(ret, discovered[next]);
        }
    }
    
    if(ret == discovered[now]){
        ll m = 0;
        bool in_sccrest = false;
        while(true){
            int temp = stk.back();
            stk.pop_back();
            sccnum[temp] = sccCounter;
            m += money[temp];
            if(is_rest[temp]) in_sccrest = true;
            if(temp == now) break;
        }
        sccmoney[sccCounter] = m;
        if(in_sccrest) is_sccrest[sccCounter] = true;
        sccCounter++;
    }
    
    return ret;
}
 
void make_sccgraph(){
    for(int i = 1; i <= N; i++){
        for(auto &w : adj[i]){
            if(sccnum[w] == sccnum[i]) continue;
            sccgraph[sccnum[i]].push_back(sccnum[w]);
        }
    }
}
 
ll getmaxmoney(int nowscc){
    ll &ret = sccmaxmoney[nowscc];
    if(ret != -1) return ret;
    
    if(sccgraph[nowscc].empty()){
        if(is_sccrest[nowscc]) return ret = sccmoney[nowscc];
        else return ret = 0;
    }
    
    ret = sccmoney[nowscc];
    ll temp = 0;
    
    for(int i = 0; i < sccgraph[nowscc].size(); i++){
        int nextscc = sccgraph[nowscc][i];
        temp = max(temp, getmaxmoney(nextscc));
    }
    
    if(temp == 0 && !is_sccrest[nowscc]) return ret = 0;
 
    return ret += temp;
}
 
void solve(){
    for(int i = 1; i <= N; i++){
        if(discovered[i] == -1){
            SCC(i);
        }
    }
    
    make_sccgraph();
    
    ll res = getmaxmoney(sccnum[S]);
    cout << res << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}