백준 4013 ATM (c++) : 피너클

4013번: ATM

https://www.acmicpc.net/problem/4013

 

SCC로 뭉치고 다시 그래프로 만든다음 dp를 이용해서 풀었다.

int n, m;
vector<int> graph[500001];
long long money[500001];
bool isR[500001];

입력부분에서 사용할 변수들이다.

isR은 현재 정점이 레스토랑인지 확인하는 용도이고 money는 해당 정점이 갖고 있는 돈이다.

int cnt = 0;
int dfsn[500001];
bool finished[500001];
vector<int> stack;
int sn[500001];
int SN = 0;
vector<vector<int>> SCC;
long long sn_money[500001] = { 0, };
bool sn_R[500001];

이것들은 SCC에 사용해줄 놈들이다.

아래 있는 sn_money와 sn_R은 SCC로 뭉쳐놓은 정점들에 사용해줄 놈들이다.

	memset(cache, -1, sizeof(cache));

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
	}
	for (int i = 1; i <= n; i++) {
		cin >> money[i];
	}
	int s, p;
	cin >> s >> p;
	for (int i = 0; i < p; i++) {
		int a;
		cin >> a;
		isR[a] = true;
	}

일단 값들을 입력 받아준다. graph에는 단반향으로 넣어주고 money에는 각 정점이 갖고 있는 돈이 들어간다.

isR[1]이 true라면 1번 정점은 레스토랑이라는 의미이다.

 

	for (int i = 1; i <= n; i++) if (dfsn[i] == 0) dfs(i);

이제 정점들 전부 돌아보며 SCC를 만들어주면 된다.

 

int dfs(int now) {
	dfsn[now] = ++cnt;
	stack.push_back(now);

	int parent = dfsn[now];
	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];

		if (dfsn[next] == 0) parent = min(parent, dfs(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}

	if (parent != dfsn[now]) return parent;

	vector<int> scc;
	while (!stack.empty()) {
		int t = stack.back();
		stack.pop_back();
		scc.push_back(t);
		
		sn[t] = SN;
		finished[t] = true;
		sn_money[SN] += money[t];
		if (isR[t]) sn_R[SN] = true;

		if (t == now) break;
	}

	SCC.push_back(scc);
	SN++;
	return parent;
}

그냥 일반적인 SCC코드와 똑같지만

	while (!stack.empty()) {
		int t = stack.back();
		stack.pop_back();
		scc.push_back(t);
		
		sn[t] = SN;
		finished[t] = true;
		sn_money[SN] += money[t];
		if (isR[t]) sn_R[SN] = true;

		if (t == now) break;
	}

여기에서 sn_money와 sn_R을 업데이트해준다.

같은 SCC안에 들어가는 모든 정점의 돈을 넣어주고

같은 SCC안에 들어가는 정점중 하나라도 레스토랑이면 sn_R을 true로 해준다.

 

	for (int i = 1; i <= n; i++) if (dfsn[i] == 0) dfs(i);
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++) if (!visited[i]) makeDAG(i);

이제 SCC를 만들었으면 SCC로 뭉친 놈들을 이용해서 다시 그래프를 만들어준다.

bool visited[500001];
vector<int> v[500001];
void makeDAG(int now) {
	visited[now] = true;

	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if (sn[now] != sn[next]) {
			v[sn[now]].push_back(sn[next]);
		}
		if (!visited[next]) makeDAG(next);
	}
}

현재 정점의 SN과 다음 정점의 SN이 다르다면 v에 넣어준다.

SN은 SCC_Number이다.

이렇게 하면 SN을 이용한 그래프가 만들어진다.

 

	for (int i = 1; i <= n; i++) if (dfsn[i] == 0) dfs(i);
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++) if (!visited[i]) makeDAG(i);

	cout << solve(sn[s]) << '\n';

이제 출발점인 s의 SN에서 solve함수를 돌리면 끝이다.

long long cache[500001];

long long solve(int now) {
	if (v[now].size() == 0) {
		if (sn_R[now]) return sn_money[now];
		else return -98765432100;
	}

	long long& ret = cache[now];
	if (ret != -1) return ret;

	bool nowR = sn_R[now];

	if (nowR) {
		long long nowMoney = sn_money[now];
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}
	else {
		long long nowMoney = -98765432100;
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}
}

solve함수다. 

long long solve(int now) {
	if (v[now].size() == 0) {
		if (sn_R[now]) return sn_money[now];
		else return -98765432100;
	}

현재 정점에서 더 나아갈 곳이 없다면 바로 return을 해주는데

현재 정점안에 레스토랑이 있다면 정점의 돈을 전달하고

아니면 최대한 낮은 숫자를 전달한다. 이렇게 하면 이 정점을 선택하지 않는 선택을 이전의 정점이 할것이다.

	long long& ret = cache[now];
	if (ret != -1) return ret;

	bool nowR = sn_R[now];

만약 이 정점에 도달한적이 있다면 확인한번 해주고

아니면 nowR을 준비해준다. nowR은 큰 역할을 하는건 아니지만 그냥 보기 좋으라고 했다.

	if (nowR) {
		long long nowMoney = sn_money[now];
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}

만약 현재 정점안에 레스토랑이 있다면

nowMoney는 현재 정점의 돈으로 해준다.

그 후 다음의 모든 정점을 확인해주며 nowManey와 solve(next) + sn_money[now]를 비교해준다.

max(현재 그대로 가는것, 현재 정점을 선택하고 다음 정점중 최대를 선택하는것) 를 비교하는 것이다.

다음 정점중 최대를 선택하기 위해서는 무조건 현재 정점을 선택해야한다.

nowMoney를 선택하는 것은 다음 정점을 선택하지 않고 현재 정점만을 이용하겠단 의미이다.

	else {
		long long nowMoney = -98765432100;
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}
}

현재 정점 안에 레스토랑이 없다면?

nowMoney에는 최대한 낮은 돈을 넣어준다.

다른 레스토랑이 있는 정점에 도달하기 전까지는 이 정점의 돈은 사용하지 못한다.

max(현재 그대로 가는것, 현재 정점을 선택하고 다음 정점중 최대를 선택하는것) 를 비교하는 것이다.

여기서 현재 그대로 가는것이 중요하다. 

현재 정점에는 레스토랑이 없다. 즉 이 정점의 돈은 바로 사용하지 못한다. 다른 레스토랑이 있는 정점에 도달해야 사용 가능하다.

 

만약 여기서 nowMoney를 0으로 설정한다면 그건 잘못된것이다.

우리는 맨처음에 

	if (v[now].size() == 0) {
		if (sn_R[now]) return sn_money[now];
		else return -98765432100;
	}

이걸 설정했다. 만약 마지막 정점이 레스토랑이 아니면 마이너스의 낮은 숫자를 반환하게 설정했다.

만약 nowMoney를 0으로 설정하면 현재정점을 이용하는 것이 아닌 건너뛰어버리는 것이 된다.

 

현재 정점이 레스토랑이 아니고 다음 정점도 레스토랑이 아니다. 앞으로 쭉 레스토랑이 아니다.

nowMoney = max(nowMoney, solve(next) + sn_money[now]);

solve(next) + sn_money[now]는 다음 정점에서 얻을수 있는 가장 큰 돈 + 현재 정점의 돈 이라는 의미이다.

우리는 마지막 정점에서 -98765432100을 반환하게 설정했다.

만약 nowMoney가 0이라면 어떻게 될까

solve(next)에서 -98765432100이 반환되었고 sn_money는 그것보다 작은 값이다. 즉 -값이다.

nowMoney는 0이고 solve(next) + sn_money[now]는 -이니 둘을 max하면 0이 반환된다.

결국 0이 반환되게 된다.

 

근데 solve(now)가 0을 반환한다는 것은 now이전의 정점의 입장에서는 solve(next)가 0을 반환하는게 된다.

그럼 nowMoney=0, solve(next) = 0 + sn_money[now]를 비교하게 되어 뒤의것이 채택되게 된다.

뒤의 정점들은 레스토랑이 아니어서 사용하면 안되지만 nowMoney를 0으로 설정했기에 건너뛰어버리게 되는것이다.

 

그래서 -98765432100으로 초기화한것이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
vector<int> graph[500001];
long long money[500001];
bool isR[500001];

int cnt = 0;
int dfsn[500001];
bool finished[500001];
vector<int> stack;
int sn[500001];
int SN = 0;
vector<vector<int>> SCC;
long long sn_money[500001] = { 0, };
bool sn_R[500001];

int dfs(int now) {
	dfsn[now] = ++cnt;
	stack.push_back(now);

	int parent = dfsn[now];
	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];

		if (dfsn[next] == 0) parent = min(parent, dfs(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}

	if (parent != dfsn[now]) return parent;

	vector<int> scc;
	while (!stack.empty()) {
		int t = stack.back();
		stack.pop_back();
		scc.push_back(t);
		
		sn[t] = SN;
		finished[t] = true;
		sn_money[SN] += money[t];
		if (isR[t]) sn_R[SN] = true;

		if (t == now) break;
	}

	SCC.push_back(scc);
	SN++;
	return parent;
}

bool visited[500001];
vector<int> v[500001];
void makeDAG(int now) {
	visited[now] = true;

	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if (sn[now] != sn[next]) {
			v[sn[now]].push_back(sn[next]);
		}
		if (!visited[next]) makeDAG(next);
	}
}

long long cache[500001];

long long solve(int now) {
	if (v[now].size() == 0) {
		if (sn_R[now]) return sn_money[now];
		else return -98765432100;
	}

	long long& ret = cache[now];
	if (ret != -1) return ret;

	bool nowR = sn_R[now];

	if (nowR) {
		long long nowMoney = sn_money[now];
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}
	else {
		long long nowMoney = -98765432100;
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			nowMoney = max(nowMoney, solve(next) + sn_money[now]);
		}
		return ret = nowMoney;
	}
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	memset(cache, -1, sizeof(cache));

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
	}
	for (int i = 1; i <= n; i++) {
		cin >> money[i];
	}
	int s, p;
	cin >> s >> p;
	for (int i = 0; i < p; i++) {
		int a;
		cin >> a;
		isR[a] = true;
	}

	for (int i = 1; i <= n; i++) if (dfsn[i] == 0) dfs(i);
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++) if (!visited[i]) makeDAG(i);

	cout << solve(sn[s]) << '\n';


	return 0;
}

전체코드다.