백준 5847번: Milk Scheduling (C++)

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

5847번: Milk Scheduling

---

Solved By: Topological Sort, DP

 

어떤 소 B는 소 A가 우유를 먹기 전까지는 절대 못 먹습니다. A가 먹어야 B의 먹을 순서가 된다는 뜻은 Topological Sort를 사용해 모든 소들의 순서 관계를 파악해야 합니다. 그 과정에서 각 소가 먹는 데에 걸리는 시간이 있고, 모든 소가 먹기까지의 걸리는 시간을 구해야 합니다.

Topological Sort를 구하는 과정에서 DP를 돌려 최댓값을 구하면 되는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10001
#define INF 1e9
using namespace std;

int cost[MAX];
int indegree[MAX];
vector<int> adj[MAX];
vector<int> cache(MAX, 0);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> cost[i];
    
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        indegree[b]++;
    }
    
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(!indegree[i]){
            q.push(i);
            cache[i] = cost[i];
        }
    }
    
    int result = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            
            cache[next] = max(cache[next], cache[now] + cost[next]);
            if(--indegree[next] == 0){
                q.push(next);
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        result = max(result, cache[i]);
    }
    
    cout << result;
    return 0;
}