1일1알

백준 2056번 작업 C++ 본문

알고리즘

백준 2056번 작업 C++

영춘권의달인 2022. 10. 10. 11:31

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

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

 

위상 정렬

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
vector<int> inDegree;
vector<int> times;
vector<int> res;
vector<vector<int>> graph;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    inDegree = vector<int>(n + 1, 0);
    times = vector<int>(n + 1);
    res = vector<int>(n + 1, 0);
    graph = vector<vector<int>>(n + 1, vector<int>());

    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        times[i] = t;
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int before;
            cin >> before;
            graph[before].push_back(i);
            inDegree[i]++;
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    int ans = 0;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (auto next : graph[curr]) {
            res[next] = max(res[next], res[curr] + times[curr]);
            if (--inDegree[next] == 0) q.push(next);
        }
    }
    for (int i = 1; i <= n; i++) {
        res[i] += times[i];
        ans = max(ans, res[i]);
    }
    cout << ans;
}
저작자표시

'알고리즘' 카테고리의 다른 글

백준 17352번 여러분의 다리가 되어 드리겠습니다! C++  (0) 2022.10.12
백준 10974번 모든 순열 C++  (0) 2022.10.11
백준 5397번 키로거 C++  (0) 2022.10.09
백준 1699번 제곱수의 합 C++  (0) 2022.10.08
백준 17822번 원판 돌리기 C++  (0) 2022.10.04
'알고리즘' Related Articles more