문제
https://www.acmicpc.net/problem/4013
문제해설
길어서 링크 참조
문제풀이
이 문제는 SCC와 위상정렬 BFS가 섞여있는 문제이다.
보통 SCC가 심화되면 위상정렬과 엮이게 된다.
왜냐하면 SCC들을 묶어서 그래프를 새로 만들게 되면
그 그래프는 사이클이 없는 방향 그래프가 되기 때문이다.
이 문제를 풀기 위해 첫번째로 해야할 일은 SCC를 만드는 것이다.
SCC를 만드는 과정에서 SCC로 묶인 노드들을 하나로 만들어 줄 것이기 때문에
레스토랑이 있는지 유뮤와 ATM에 있는 돈들 또한 하나로 묶어야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (parent == discover[now]) {
vector<int>tmp;
while (true) {
int here = st.top();
st.pop();
scc[here] = scc_cnt;
tcost[scc_cnt] += cost[here];
if (restaurant[here])
scc_restaurant[scc_cnt] = 1;
if (start == here)
scc_start = scc_cnt;
tmp.push_back(here);
if (here == now)
break;
}
scc_cnt++;
}
SCC 과정 내에서 위와 같은 처리를 해줘야 한다.
SCC가 만들어지면 SCC로 묶인 새로운 그래프를 만들어 줘야한다.
1
2
3
4
5
6
for (int now = 1; now <= n; now++) {
for (int i = 0; i < arr[now].size(); i++) {
if (scc[now] != scc[arr[now][i]])
scc_arr[scc[now]].push_back(scc[arr[now][i]]);
}
}
그 과정이 위의 코드이다.
scc_arr라는 새로운 그래프를 만들어준다.
그 다음은 BFS를 통해 최대의 돈을 모으는 과정을 진행한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bfs() {
money[q.front()] = tcost[q.front()];
while (!q.empty()) {
int now = q.front();
q.pop();
if (scc_restaurant[now])
res = max(res, money[now]);
for (int i = 0; i < scc_arr[now].size(); i++) {
int next = scc_arr[now][i];
if (money[next] < money[now] + tcost[next]) {
money[next] = money[now] + tcost[next];
q.push(next);
}
}
}
}
사이클이 없는 방향 그래프이기 때문에 방문처리는 하지않아도 된다.
돈의 최대값을 계속 갱신하여 BFS가 끝나면 출력해준다.
주의할 점은 이 문제에는 시작지점이 존재한다.
그렇기 때문에 SCC를 만들 때에도 시작지점을 신경써줘야 한다.
전체코드
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
vector<vector<int>>arr;
vector<vector<int>>scc_arr;
vector<int>restaurant, scc_restaurant;
int cost[500001], tcost[500001], discover[500001], scc[500001], money[500001];
int cnt, scc_cnt = 1, res, start, scc_start;
stack<int>st;
queue<int>q;
int dfs(int now) {
st.push(now);
discover[now] = cnt++;
int parent = discover[now];
for (int i = 0; i < arr[now].size(); i++) {
int next = arr[now][i];
if (discover[next] == -1)
parent = min(parent, dfs(next));
else if (scc[next] == -1)
parent = min(parent, discover[next]);
}
if (parent == discover[now]) {
while (true) {
int here = st.top();
st.pop();
scc[here] = scc_cnt;
tcost[scc_cnt] += cost[here];
if (restaurant[here])
scc_restaurant[scc_cnt] = 1;
if (start == here)
scc_start = scc_cnt;
if (here == now)
break;
}
scc_cnt++;
}
return parent;
}
void bfs() {
money[q.front()] = tcost[q.front()];
while (!q.empty()) {
int now = q.front();
q.pop();
if (scc_restaurant[now])
res = max(res, money[now]);
for (int i = 0; i < scc_arr[now].size(); i++) {
int next = scc_arr[now][i];
if (money[next] < money[now] + tcost[next]) {
money[next] = money[now] + tcost[next];
q.push(next);
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m; cin >> n >> m;
arr.resize(n + 1);
scc_arr.resize(n + 1);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
arr[a].push_back(b);
}
for (int i = 1; i <= n; i++) {
int x; cin >> x;
cost[i] = x;
}
int p; cin >> start >> p;
restaurant.resize(n + 1);
scc_restaurant.resize(n + 1);
for (int i = 0; i < p; i++) {
int x; cin >> x;
restaurant[x] = 1;
}
fill(discover, discover + 500001, -1);
fill(scc, scc + 500001, -1);
for (int i = 1; i <= n; i++) {
if (discover[i] == -1)
dfs(i);
}
for (int now = 1; now <= n; now++) {
for (int i = 0; i < arr[now].size(); i++) {
if (scc[now] != scc[arr[now][i]])
scc_arr[scc[now]].push_back(scc[arr[now][i]]);
}
}
q.push(scc_start);
bfs();
cout << res;
return 0;
}