(4013) ATM

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

단계별로 풀어보기

48단계(강한 연결 요소) 4번째

 

 

 

SCC를 기준으로 도시를 묶은 뒤, 위상정렬된 순서로 DP를 적용시킨다. 레스토랑이 있는 도시가 속한 SCC에 해당하는 DP값들 중 최대값을 구하면 된다.

타잔 알고리즘에서 SCC를 구성하는 순서가 위상 정렬의 역순이므로 위상 정렬 알고리즘을 쓸 필요 없이 SCC를 역순으로 탐색하면 된다. 단 시작 도시는 정해져 있기 때문에, 시작 도시가 속한 SCC에 해당하는 DP배열만 값을 초기화하고 이 도시SCC에서 갈 수 있는 도시SCC부터 갱신을 시작해 갈 수 없는 도시에서는 DP값이 갱신되지 않도록 한다.

 

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, s, p, cnt= 1, idx= 1, ans= 0;
  
  cin >> n >> m;
  
  vector<int> check(n+1), scc(n+1);
  vector adj(n+1, vector<int> ());
  stack<int> st;
  
  while(m--){
    int x, y;
    
    cin >> x >> y;
    
    adj[x].push_back(y);
  }
  
  auto dfs= [&](auto self, int now) -> int {
    st.push(now);
    check[now]= cnt++;
    int low= check[now];
    
    for(int next:adj[now]){
      if(!check[next]){
        low= min(low, self(self, next));
      }else if(!scc[next]){
        low= min(low, check[next]);
      }
    }
    
    if(check[now]==low){
      while(true){
        int here= st.top();
        st.pop();
        scc[here]= idx;
        
        if(here==now)  break;
      }
      
      idx++;
    }
    
    return low;
  };
  
  for(int i=1;i<=n;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//
  
  vector<int> cash(idx), dp(idx, -1);
  vector sccadj(idx, vector<int> ());
  
  for(int i=1;i<=n;i++){
    int c;
    
    cin >> c;
    
    cash[scc[i]]+= c;
  }
  
  cin >> s >> p;
  
  dp[scc[s]]= cash[scc[s]];
  
  for(int i=1;i<=n;i++){
    for(int j:adj[i]){
      if(scc[i]!=scc[j]){
        sccadj[scc[i]].push_back(scc[j]);
      }
    }
  }
  
  for(int now=idx-1;now>=0;now--){
    if(dp[now]==-1)  continue;
    
    for(int next:sccadj[now]){
      dp[next]= max(dp[next], dp[now]+cash[next]);
    }
  }
  
  while(p--){
    int x;
    
    cin >> x;
    
    ans= max(ans, dp[scc[x]]);
  }
  
  cout << ans;
  
  return 0;
}