백준 2056 - 작업

작업 간 선행관계가 제시되어 있으므로 작업들의 관계는 DAG가 되고 DP를 통해 각 작업을 끝내는데 필요한 최소시간을 찾아 더해주면 된다.

 

포레스트 형태에 대해 유의하여 구현한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using graph = vector<vector<int>>;

int finished[100001];
int fee[100001];
int memo[100001];

int dp(int node, graph &al);

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    
    memset(memo, -1, sizeof memo);
    graph task(n + 1);
    
    for (int i = 0; i < n; ++i)
    {
        int indegree;
        cin >> fee[i + 1] >> indegree;
        
        for (int j = 0; j < indegree; ++j)
        {
            int node;
            cin >> node;
            task[i + 1].push_back(node);
        }
    }
    
    int res = 0;
    
    for (int k = n; k > 0; --k)
        if (!finished[k])
            res = max(res, dp(k, task));

    cout << res;
}

int dp(int node, graph &al)
{
    int &ret = memo[node];
    
    if (ret != -1)
        return ret;
    
    if (!al[node].size())
    {
        finished[node] = 1;
        return ret = fee[node];
    }

    for (auto item : al[node])
        ret = max(ret, dp(item, al));

    finished[node] = 1;
    return ret += fee[node];
}