-
[BOJ] 2152 : 여행 계획 세우기
2152 : 여행 계획 세우기 풀이 주어진 그래프에서 scc를 구해서, 각 컴포넌트를 노드로 하는 새로운 그래프를 만들자 scc로 구성된 그래프는 항상 DAG이다 여기서 위상정렬 같은 느낌으로 dp? 같은 느낌으로 으쌰으쌰 하자 타잔으로 scc를 구하면 위상정렬의 역순으로 컴포넌트를 구하게 된다 아몰랑 코드 #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = 1e4 + 10; int n, m, s, e; int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN]; vi gph[MAXN]; vector<vi> res; int dfs(int now) {...
-
[BOJ] 16169 : 수행 시간
16169 : 수행 시간 풀이 위상정렬 acm craft인가 그 문제랑 똑같은 것 같다. (사실 기억 안 남 ㅎ) 잘 짜주면 된다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, dap, l[101], t[101], d[101], r[101]; struct edg { int idx, dst; }; vector<edg> gph[101]; void go(int now) { dap = max(dap, r[now]); for (edg nxt : gph[now]) { r[nxt.idx] = max(r[nxt.idx], r[now] + t[nxt.idx] + nxt.dst); if (!(--d[nxt.idx])) go(nxt.idx); } } int...
-
[BOJ] 2056 : 작업
2056 : 작업 풀이 간단한 다이나믹으로 풀어도 되고 위상정렬스럽게 풀어도 된다 코드 #include <cstdio> #include <algorithm> using namespace std; int n, res, dp[10001]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int c, m, x; scanf("%d %d", &c, &m); for (int j = 0; j < m; j++) { scanf("%d", &x); dp[i] = max(dp[i], dp[x]); } res = max(res, dp[i] += c); } printf("%d", res); return 0; }...
-
[BOJ] 1005 : ACM Craft
1005 : ACM Craft 풀이 위상딱 위상딱 신나는 노래 나도 한 번 불러본다~ 코드 #include <iostream> #include <string.h> #include <vector> using namespace std; const int n_ = 1e3 + 3; int req[n_], dst[n_], idg[n_], ans[n_]; vector<int> gph[n_]; void dfs(int now) { idg[now]--; for (int nxt : gph[now]) { ans[nxt] = max(ans[nxt], ans[now] + req[nxt]); if (!(--idg[nxt])) dfs(nxt); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc; cin >> tc; while (tc--) { int n, k, w;...
-
[BOJ] 9466 : 텀 프로젝트
9466 : 텀 프로젝트E 풀이 위상정렬을 하자! 코드 #include <stdio.h> #include <memory.h> const int n_ = 100000 + 1; int ans, a[n_], idg[n_]; bool chk[n_]; void dfs(int n) { chk[n] = true; ++ans, --idg[a[n]]; if (!chk[a[n]] && !idg[a[n]]) dfs(a[n]); } int main() { int t, n, i, j; scanf("%d", &t); for (i = 1; i <= t; ++i) { ans = 0; scanf("%d", &n); memset(chk, 0, sizeof(chk)); memset(idg, 0, sizeof(idg)); for (j = 1; j...
-
[BOJ] 2623 : 음악프로그램
2623 : 음악프로그램 풀이 위상정렬을 하면 된다! 코드 #include <iostream> #include <vector> using namespace std; const int n_ = 1000 + 3; int n, m, idg[n_]; vector<int> ans; vector<int> edg[n_]; void dfs(int now) { idg[now] = -1; ans.push_back(now); for (auto nxt : edg[now]) if (!(--idg[nxt])) dfs(nxt); } int main() { int i, j, a, b, c; cin >> n >> m; while (m--) { cin >> a >> b; while (--a) { cin >> c;...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...
-
[BOJ] 1948 : 임계경로
1948 : 임계경로 풀이 문제를 다르게 생각해보자. 마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다. 따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다! 풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야 코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다. get_max_len() 함수를 보면 일단 카운팅하기 전에...