[백준/BOJ] 백준 4013번 : ATM

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

4013번: ATM

타잔 알고리즘을 이용하여 SCC를 구하고 SCC들 사이의 그래프를 만든다. 그리고 출발지 SCC에서 다익스트라를 이용해 각 SCC까지 갈 때 얻을 수 있는 최대 돈을 구하고, 아웃백이 있는 SCC 중 최대 값을 구해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
using namespace std;

int n, m;
vector<int> adj[500001];
vector<int> atm(500001, 0);
int s;
int p;
vector<int> outback;
int output;

vector<int> visited(500001, 0);
vector<int> maked(500001, 0);
vector<int> node_number(500001);
int node_id_cnt = 0;
stack<int> st;
int scc_id_cnt = 0;
vector<int> scc_id(500001); //각 정점이 어떤 scc에 속해있는지 표시 [정점] = scc의 ID
vector<int> scc_sum(500001); //[scc의 ID] = 속한 정점의 돈들의 합
vector<int> scc_adj[500001]; //scc끼리의 그래프
vector<int> scc_outback(500001); //아웃백이 속한 scc 표시

//강한 연결 요소(SCC) 타잔 알고리즘을 사용하여 SCC를 구한다

int Dfs(int here)
{
	visited[here] = 1;

	node_id_cnt++;
	node_number[here] = node_id_cnt;

	st.push(here);

	int parent = node_number[here];

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		if (visited[there] == 0)
		{
			parent = min(parent, Dfs(there));
		}

		else if (maked[there] == 0)
		{
			parent = min(parent, node_number[there]);
		}
	}

	if (parent == node_number[here])
	{
		int this_sum = 0;
		scc_id_cnt++;

		while (1)
		{
			int top_node = st.top();
			st.pop();

			scc_id[top_node] = scc_id_cnt;
			this_sum += atm[top_node];
			maked[top_node] = 1;

			if (top_node == here)
				break;
		}

		scc_sum[scc_id_cnt] = this_sum;
	}

	return parent;
}

//다익스트라를 이용한다
int Solve(int start)
{
	int ret = 0;

	vector<int> max_value(500001, -1); //해당 정점에서 최댓값을 저장
	priority_queue<pair<int, int>> pq;

	max_value[start] = scc_sum[start];
	pq.push(make_pair(scc_sum[start], start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = pq.top().first;
		pq.pop();

		if (here_cost < max_value[here])
			continue;

		for (int i = 0; i < scc_adj[here].size(); i++)
		{
			int there = scc_adj[here][i];
			int there_cost = here_cost + scc_sum[there];

			//더 큰 값을 찾았을때
			if (max_value[there] < there_cost)
			{
				max_value[there] = there_cost;
				pq.push(make_pair(there_cost, there));
			}
		}
	}

	for (int i = 1; i <= scc_id_cnt; i++)
	{
		//아웃백이 있는 scc중 가장 큰 값을 구한다
		if (scc_outback[i] == 1)
		{
			ret = max(ret, max_value[i]);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)
	{
		int money;
		cin >> money;

		atm[i] = money;
	}

	cin >> s >> p;

	for (int i = 0; i < p; i++)
	{
		int input;
		cin >> input;

		outback.push_back(input);
	}

	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == 0)
		{
			Dfs(i);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			int here = i;
			int there = adj[i][j];

			//다른 그룹의 scc일때
			if (scc_id[here] != scc_id[there])
			{
				scc_adj[scc_id[here]].push_back(scc_id[there]);
			}
		}
	}

	//아웃백이 있는 scc 그룹은 체크
	for (int i = 0; i < outback.size(); i++)
	{
		scc_outback[scc_id[outback[i]]] = 1;
	}

	output = Solve(scc_id[s]);

	cout << output;

	return 0;
}