백준 4013 : ATM

문제 링크

SCC를 이용하여 해결하였다.

같은 정점, 간선을 여러번 사용할 수 있고, 최대 뽑을수 있는 현금을 계산해야 하기 때문에 어떤 정점에 방문했을 때, 그 정점이 속한 scc를 모두 방문하고 와야 한다. 따라서 scc중 한 점을 방문하는 것은 scc에 있는 모든 정점을 방문하는 것과 같으므로 그래프를 압축시켜 scc끼리의 그래프로 생각해볼 수 있다. 이러면 문제는 압축시킨 그래프에서 시작점에서 갈 수 있는 최장 거리를 구하는 것으로 바뀐다.

압축시킨 그래프는 DAG, 즉 사이클 없는 방향 그래프 라는 것이 알려져 있고, DAG에서 어떤 점에서의 최장거리를 구하기 위해서는 위상정렬을 한 후에, 차례대로 순회하면서 메모이제이션을 이용해 최장거리를 갱신해 주면 된다. 여기서 scc를 구할 때, dfs를 사용했으므로, dfs함수의 종료 순서의 역순이 위상정렬 순서라는 것을 이용해서 해결해주면 좀 더 쉽게 해결할 수 있다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

int n,m;

vector<int> money;
vector<bool> rest;
vector<vector<int>> edge;
vector<int> discovered;
vector<vector<int>> scc;
vector<int> sccidx;
vector<bool> finished;
stack<int> st;
vector<int> earn;
vector<int> dp;

int s,P;
int discovcnt = 0;
int scccnt = 0;
int ans = 0;

int findscc(int cur)
{
   discovered[cur] = discovcnt++;
   int ret= discovered[cur];
   st.push(cur);

   for(auto next : edge[cur])
   {
       if(discovered[next] == -1)
       {
           ret= min(ret,findscc(next));
       }
       else if(!finished[next])
       {
           ret = min(ret,discovered[next]);
       }
   }    

   if(ret >= discovered[cur] && !finished[cur])
   {
       scc.push_back(vector<int>());
       while(1)
       {
           int stop = st.top();
           st.pop();

           money[scccnt] += earn[stop];
           sccidx[stop] = scccnt;
           scc[scccnt].push_back(stop);
           finished[stop] = true;

           if(stop == cur) break;
       }

       scccnt++;
   }

   return ret;
}

int main()
{
   ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
   cin>>n>>m;

   edge = vector<vector<int>>(n);
   rest = vector<bool>(n,false);
   discovered = vector<int>(n,-1);
   sccidx = vector<int>(n);
   finished = vector<bool>(n,false);
   earn = vector<int>(n,0);
   money = vector<int>(n,0);
   dp = vector<int>(n,0);
  
   for(int i = 0;i<m;i++)
   {
       int v1,v2;
       cin>>v1>>v2;
       v1--; v2--;
       edge[v1].push_back(v2);
   }

   for(int i = 0;i<n;i++)
   {
       cin>>earn[i];
   }

   cin>>s>>P;

   s--;

   for(int i = 0;i<P;i++)
   {
       int r;
       cin>>r;
       r--;

       rest[r] = true;
   }

   findscc(s);
   dp[scccnt-1] = money[scccnt-1];

   for(int i = scccnt-1;i>=0;i--)
   {
       for(auto elem : scc[i])
       {
           for(auto next : edge[elem])
           {
               if(sccidx[next] != i)
               {
                   dp[sccidx[next]] = max(dp[sccidx[next]],dp[i] + money[sccidx[next]]);
               }
           }
       }        
   }

   for(int i = 0;i<n;i++)
   {
       if(rest[i] && discovered[i] != -1)
       {
           ans = max(ans,dp[sccidx[i]]);
       }
   }

   cout<<ans;  

   return 0;
}