백준 2152번: 여행 계획 세우기
여행 계획 세우기
아이디어
ATM 문제랑 비슷하다, 같은 SCC에 속하는 여행지는 모두 방문하고, 다음 SCC로 이동한다. 시작 지점에서 도달 가능한지 확인하고, 도달 가능하면 금액을 갱신한다.
코드
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 10001;
int N, M, S, T, cnt, scnt;
int discovered[MAX], sccn[MAX];
bool finished[MAX];
vector<vector<int>> adj, scc;
stack<int> s;
int dfs (int cur) {
s.push(cur);
discovered[cur] = ++cnt;
int ret = discovered[cur];
for (int next : adj[cur]) {
if (!discovered[next]) {
ret = min(ret, dfs(next));
}
else if (!finished[next]) {
ret = min(ret, discovered[next]);
}
}
if (ret == discovered[cur]) {
vector<int> v;
while (1) {
int t = s.top();
s.pop();
sccn[t] = scnt;
finished[t] = true;
v.push_back(t);
if (t == cur) break;
}
scc.push_back(v);
scnt++;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> S >> T;
adj = vector<vector<int>>(N+1);
while (M--) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
for (int i = 1; i < N+1; i++) {
if (!discovered[i]) dfs(i);
}
vector<vector<int>> sccadj(scc.size());
vector<int> indegree(scc.size(), 0);
for (int i = 1; i < N+1; i++) {
for (int next : adj[i]) {
if (sccn[i] != sccn[next]) {
sccadj[sccn[i]].push_back(sccn[next]);
indegree[sccn[next]]++;
}
}
}
int start = sccn[S];
int end = sccn[T];
vector<int> count(scc.size());
queue<int> q;
for (int i = 0; i < scc.size(); i++) {
if (!indegree[i]) q.push(i);
}
for (int i = 0; i < scc.size(); i++) {
count[i] = scc[i].size();
}
vector<int> can(scc.size());
can[start] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == end) break;
for (int next : sccadj[cur]) {
if (can[cur]) {
count[next] = max(count[next], count[cur]+(int)scc[next].size());
can[next] = true;
}
if (!--indegree[next]) q.push(next);
}
}
if (can[end]) cout << count[end] << '\n';
else cout << 0 << '\n';
return 0;
}
여담
당연한 얘기지만 위상정렬 할 때 그냥 시작 지점을 넣으면 안된다. 도달 가능 여부를 확인하는 배열을 선언하고, 해당하는 SCC에 도달한 경우, 다음 SCC도 도달 가능하다고 표시해준다.
Author And Source
이 문제에 관하여(백준 2152번: 여행 계획 세우기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-2152번-여행-계획-세우기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)