Topological_sort

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17227 🧐 관찰 및 접근 # 생각하기 쉽게, $N$번 주제인 “그팩주” 근처에서 생각해보자. 어떤 정점에서, 다음 정점 중 $N$번 정점이 있다면 준표는 화제를 그 정점으로 보내면 안된다. 만영이의 차례에서 만영이는 다음 간선중 최대한 기댓값이 높은 정점으로 가려고 한다. 그것들을 하나하나 반려해가는 맛인데.. DP식을 이런식으로 세울 수 있을까? $\text{DP}[i][a]$ : $i$번 정점에서 $a$번사람의 턴일때 기댓값 $\text{DP}[i][jun] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][man])$ $\text{DP}[i][man] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][jun] + cnt)$ 예를들어 만영이가 고르 수 있는 다음 정점이 $N, i, j, k$라고 하고, 기댓값은 각각 $1e9, 10, 10, 9$라고 하자. $N$은 고르면 안되므로, 무조건 반려한다. 그러면 만영이는 10을 고르고, 이때 기댓값은 11이다. 마지막 9를 고르기 위해 3번 반려해버리면 오히려 기댓값이 12이므로, 그러면 안된다! 따라서 내림차순으로 정렬한뒤 인덱스를 더해서 정리해보자. ![[Drawing 2026-02-12 10.30.22.excalidraw.png]] 예제 3번의 그림 💻 풀이 # 코드 (C++): int calc(int cur, int turn){ if(DP[cur][turn] != -1) return DP[cur][turn]; int &ret = DP[cur][turn]; ret = 1e9; if(turn == 0){ // 준표의 턴 for(auto nxt: links[cur]) ret = min(ret, calc(nxt, 1)); return ret; } else{ // 만영이의 턴 vector<int> v; for(auto nxt: links[cur]) v.push_back(calc(nxt, 0)); sort(all(v), greater<int>()); rep(i, 0, v.size()) ret = min(ret, v[i] + i); return ret; } } void solve(){ cin >> N >> E; rep(i, 0, E){ int u, v; cin >> u >> v; links[u].push_back(v); inDeg[v]++; } rep(i, 0, N+1) DP[i][0] = DP[i][1] = -1; DP[N][0] = 1e9; DP[N][1] = 0; int ans = 1e9; rep(i, 1, N+1) if(inDeg[i] == 0) ans = min(ans, calc(i, 1)); if(ans == 1e9) cout << -1 << '\n'; else cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4013 🧐 관찰 및 접근 # 그래프가 DAG라면 위상정렬을 하면서 DP를 진행할 수 있을텐데.. 같은 정점을 여러번 들릴 수 있으므로, 어떤 정점이 사이클 안에 들어있다면 해당 사이클 내의 ATM을 모두 들릴 수 있다! 서로 자유롭게 이동 가능한 관계라면 모두 자유롭게 들릴 수 있으므로, 이를 SCC로 묶어 DAG로 만들자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; DirectedGraph graph(N+1); rep(i, 0, M){ int u, v; cin >> u >> v; graph.add_edge(u, v); } DirectedGraph dag = graph.getCompressedGraph(); int sz = dag.V; vector<int> val(sz), DP(sz, -1e9), indeg(sz, 0); rep(i, 1, N+1){ int X; cin >> X; val[graph.sccId[i]] += X; } int S, P; cin >> S >> P; S = graph.sccId[S]; DP[S] = val[S]; rep(u, 0, sz) for(auto &v: dag.links[u]) indeg[v]++; queue<int> Q; rep(i, 0, sz) if(indeg[i] == 0) Q.push(i); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto nxt: dag.links[cur]){ DP[nxt] = max(DP[nxt], DP[cur] + val[nxt]); indeg[nxt]--; if(indeg[nxt] == 0) Q.push(nxt); } } int ans = 0; rep(i, 0, P){ int X; cin >> X; X = graph.sccId[X]; ans = max(ans, DP[X]); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 번역 문제 # Farmer John은 소들의 방목 패턴을 더 잘 관리하기 위해 농장 전체에 일방통행 소 길들을 설치했습니다. 농장은 N개의 목초지로 구성되어 있으며, 편의상 1부터 N까지 번호가 매겨져 있고, 각 일방통행 소 길은 한 쌍의 목초지를 연결합니다. 예를 들어, 목초지 X에서 목초지 Y로 연결되는 길이 있다면, 소들은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없습니다.