티스토리 뷰
문제: icpc.me/2056
a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다.
문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다.
따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <cstdio> #include <algorithm> #include <vector> using namespace std; int n, in[10002], c[10002], x, y, r; vector<vector<int>> vt; int main() { scanf("%d", &n); vt.resize(n + 1); for (int i = 1; i <= n; i++) { scanf("%d%d", &c[i], &x); for (int j = 0; j < x; j++) { scanf("%d", &y); vt[y].push_back(i); in[i]++; } } vector<int> q; for (int i = 1; i <= n; i++) { if (!in[i]) q.push_back(i); } while (q.size() != n) { vector<int> v; for (int h : q) { if (!(--c[h])) v.push_back(h); } r++; for (int h : v) { for (int g : vt[h]) { if (!(--in[g])) q.push_back(g); } } } x = 0; for (int h : q) x = max(x, c[h]); printf("%d\n", r + x); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)6091 핑크 플로이드 (0) | 2017.04.06 |
---|---|
BOJ)1826 연료 채우기 (0) | 2017.04.06 |
BOJ)2056 작업 (0) | 2017.04.06 |
BOJ)7579 앱 (0) | 2017.04.05 |
BOJ)2157 여행 (0) | 2017.04.05 |
BOJ)2618 경찰차 (2) | 2017.04.05 |
- TAG
- 위상 정렬
댓글
공지사항
- Total
- 315,368
- Today
- 35
- Yesterday
- 199
TAG
- MCMF
- 트리
- 이분 매칭
- MST
- dfs
- 그리디 알고리즘
- 수학
- disjoint-set
- BFS
- 다이나믹 프로그래밍
- KMP
- 힙
- 디닉
- 좌표 압축
- SCC
- 이분 탐색
- LCP array
- 네트워크 플로우
- 위상 정렬
- 세그먼트 트리
- lazy propagation
- 다익스트라
- partial sum
- lca
- 분할 정복
- 플로이드 워셜
- 라인 스위핑
- 에라토스테네스의 체
- Suffix Array
- brute force