[백준 4013번] ATM

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

ATM 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1046	337	186	25.585%

문제

인도의 도시 중 하나인 시루세리에는 모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 시루세리 은행의 현금입출금기(ATM)가 설치되어 있다. 시루세리에는 유명한 레스토랑 체인인 아웃백 커리 하우스가 있다. 이 레스토랑의 각 체인점들은 교차로에만 위치한다. 물론 각 교차로마다 항상 이 레스토랑 체인점이 있는 것은 아니다. 이 레스토랑은 현금만 사용할 수 있다. 

시루세리에 사는 반디치는 오늘 오후에 이 레스토랑에서 가족들과 파티를 열려고 한다. 그런데 갖고 있는 현금이 부족하여 레스토랑으로 가는 동안에 가능한 한 많은 현금을 ATM 기기로부터 인출할 계획을 세웠다. 그는 자신의 집에서 출발하여 차로 이동하면서 통과하는 모든 교차로 ATM 기기에 들어있는 현금 전부를 인출하려고 한다. 차량의 최종 목적지는 아웃백 커리 하우스 체인점 중의 한 곳이고, 이 체인점이 어떤 교차로에 위치하는지는 상관없다.

반디치는 시루세리 은행의 홈페이지 정보를 통해 각 ATM 기기에 현금이 얼마나 들어 있는지를 알고 있다. 이동 시 동일한 도로나 교차로를 여러 번 지날 수 있다. ATM 기기의 현금은 새로 보충되지 않기 때문에 첫 번째 이후 다시 방문하는 교차로의 ATM 기기에는 인출할 현금이 없다.

예를 들어, 아래 그림처럼 도시에 6개의 교차로가 있다고 하자. 교차로는 원으로 표시되어 있고, 화살표는 도로를 나타낸다. 이중 원으로 표시된 교차로에는 레스토랑이 있다. 각 ATM 기기가 갖고 있는 현금의 액수는 교차로 위에 표시된 숫자이다. 이 예에서 현금 인출을 1번 교차로부터 시작한다면, 반디치는 1-2-4-1-2-3-5의 경로를 통해서 총 47의 현금을 인출할 수 있다.

반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어진다. 여기서 S는 출발 장소(현금 인출의 시작 장소)인 교차로 번호이고 P는 레스토랑의 개수이다(1 ≤ P ≤ N). 그 다음 줄에는 각 레스토랑이 있는 교차로의 번호를 나열한 P개의 정수가 주어진다. 

각 ATM 기기에 들어 있는 현금의 액수는 0 이상 4,000 이하이다. 모든 입력에서 경로의 출발 장소로부터 일방통행 도로를 통해 도달 가능한 레스토랑이 항상 하나 이상 존재한다. 

출력

출력은 한 개의 정수이다. 이 정수는 반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수이다. 

예제 입력 1 

6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4 3 5 6

예제 출력 1 

47

너무너무 풀기 복잡했던 문제이다. 강한연결요소를 공부하고 두번째 예제로 스터디에서 해결한 문제인데 이해가 가지 않아서

여러번 다시 봐야했다. 아직 강한연결요소도 제대로 이해하지 못해서일까 많이 헤매다가 문제를 풀었다.

우선 첫째로 사이클이 생기는 부분을 SCC로 묶어서 하나의 노드처럼 만든다. 그 후에는 자연스럽게 SCC들이 위상정렬되있으므로

하나씩 방문해나가면서 가장 큰 값을 마지막에 찾아주면된다. 너무너무 복잡한 SCC세계..~~~~

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
 
using namespace std;
 
int N, M, l, k, cnt, start, SCC_num = 1;
int max_num;
 
int numbering[500001],scc_numbering[500001], scc_indegree[500001];
bool finished[500001];
stack<int> sta;
 
int atm[500001], scc_atm[500001];
bool isRestaurant[500001], scc_isRestaurant[500001];
bool cal[500001];
vector<int> v[500001], v0[500001];
queue<int> q;
 
int dfs(int);
 
int main() {
 
    cin >> N >> M;
 
    for (int i = 0; i<M; i++) {
        cin >> l >> k;
        v[l].push_back(k);
    }
 
    for (int i = 1; i<=N; i++) {
        cin >> atm[i];
    }
 
    cin >> start >> l;
 
    for (int i = 0; i<l; i++) {
        cin >> k;
        isRestaurant[k] = true;
    }
 
    for (int i = 1; i<=N; i++) {
        if (numbering[i] == 0) dfs(i);
    }
 
    for (int i = 1; i <= N; i++) {
        scc_atm[scc_numbering[i]] += atm[i];
        if (isRestaurant[i]) scc_isRestaurant[scc_numbering[i]] = true;
        if (start == i) start = scc_numbering[i];
 
        for (int j : v[i]) {
            if (scc_numbering[i] == scc_numbering[j]) continue;
            v0[scc_numbering[i]].push_back(scc_numbering[j]);
            scc_indegree[scc_numbering[j]]++;
        }    
    }
 
    for (int i = 1; i <= N; i++) {
        atm[i] = scc_atm[i];
        if (i == start) cal[i] = true;
        if (scc_indegree[i] == 0) q.push(i);
    }
 
    while (!q.empty()) {
        int num = q.front();
        q.pop();
                
        for (int i = 0; i < v0[num].size(); i++) {
            if (cal[num]) {
                atm[v0[num][i]] = max(atm[v0[num][i]], atm[num] + scc_atm[v0[num][i]]);
                cal[v0[num][i]] = true;
            }
 
            if (--scc_indegree[v0[num][i]] == 0) q.push(v0[num][i]);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (scc_isRestaurant[i] && cal[i]) max_num = max_num > atm[i] ? max_num : atm[i];
    }
 
    cout << max_num;
 
    return 0;
}
 
int dfs(int num) {
 
    numbering[num] = ++cnt;
    sta.push(num);
 
    int result = numbering[num];
    for (int i : v[num]) {
        if (numbering[i] == 0) result = min(result, dfs(i));
        else if (!finished[i]) result = min(result, numbering[i]);
    }
 
    if (result == numbering[num]) {
        while (1) {
            int t = sta.top();
            sta.pop();
            finished[t] = true;
            scc_numbering[t] = SCC_num;
            if (t == num) break;
        }
        SCC_num++;
    }
    return result;
}