[백준/BOJ] 백준 22961번 : 여행사 운영하기

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

22961번: 여행사 운영하기

해당 그래프(adj1)에서 각 정점에서 출발하여 이동 가능한 위치를 연결하는 새로운 그래프(adj2)를 만들고, adj2를 강한 연결 요소(SCC)로 만들어서 해당 SCC마다 SCC에서 가장 큰 즐거움과 가장 작은 즐거움을 저장해 놓고 SCC를 위상 정렬하여 위상 정렬의 역순을 이용해서 위상 정렬의 끝부터 답을 만들어 나가는 방식으로 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <limits>
#include <tuple>
#include <string>
#include <map>
#include <deque>
#include <stack>
#include <list>
#include <set>
using namespace std;

int n;
vector<long long> c(8001, 0);
vector<long long> d(8001, 0);
vector<pair<long long, int>> adj1[8001];
vector<vector<long long>> adj2_check(8001, vector<long long>(8001, numeric_limits<long long>::max())); //[위치1][위치2] = 위치1에서 위치2로 가는 최소 비용을 저장
vector<int> adj2[8001]; //해당 위치에서 도달할 수 있는 위치를 저장

//adj2를 강한 연결 요소 (SCC)로 만든다. 타잔 알고리즘 사용
vector<int> visited(8001, 0);
vector<int> node_id(8001, 0); //[정점] = id
vector<int> maked(8001, 0); //정점이 scc로 만들어 졌는지 확인
int id_cnt = 0;
int scc_id_cnt = 0;
vector<int> node_scc_id(8001, 0); //[정점] = scc id
vector<int> scc_adj[8001];
vector<int> scc_indgree(8001, 0);
vector<long long> scc_id_max_happy(8001, 0); //[scc id] = 해당 scc에서 가장 큰 즐거움
vector<long long> scc_id_min_happy(8001, numeric_limits<long long>::max()); //[scc id] = 해당 scc에서 가장 작은 즐거움
stack<int> st;
vector<long long> cache_max_happy(8001, 0);
vector<long long> cache_min_happy(8001, numeric_limits<long long>::max());

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

	id_cnt++;
	node_id[here] = id_cnt;

	st.push(here);

	int parent = node_id[here];

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

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

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

	//scc 하나가 완성 되는 경우
	if (parent == node_id[here])
	{
		scc_id_cnt++;

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

			node_scc_id[node] = scc_id_cnt;
			scc_id_max_happy[scc_id_cnt] = max(scc_id_max_happy[scc_id_cnt], c[node]);
			scc_id_min_happy[scc_id_cnt] = min(scc_id_min_happy[scc_id_cnt], c[node]);
			maked[node] = 1;

			if (node == here)
				break;
		}
	}

	return parent;
}



void MakeAdj2(int start, int here, long long total_cost)
{
	for (int i = 0; i < adj1[here].size(); i++)
	{
		long long there_cost = adj1[here][i].first;
		int there = adj1[here][i].second;

		if (there == start)
			continue;

		//start에서 there로 갈 수 있을때
		if (d[start] >= total_cost + there_cost)
		{
			//start에서 there로 가는 더 짧은 비용을 찾았을때
			if (adj2_check[start][there] > total_cost + there_cost)
			{
				//there 방향을 처음 확인할때
				if (adj2_check[start][there] == numeric_limits<long long>::max())
				{
					adj2[start].push_back(there);
				}

				adj2_check[start][there] = total_cost + there_cost;
				MakeAdj2(start, there, total_cost + there_cost);
			}
		}
	}
}

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

	cin >> n;

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

		c[i] = ci;
	}

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

		d[i] = di;
	}

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		long long w;

		cin >> u >> v >> w;

		adj1[u].push_back(make_pair(w, v));
		adj1[v].push_back(make_pair(w, u));
	}

	for (int i = 1; i <= n; i++)
	{
		MakeAdj2(i, i, 0);
	}

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

	//scc를 하나의 정점으로 묶어서 scc 끼리의 그래프를 만든다
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < adj2[i].size(); j++)
		{
			int here = i;
			int there = adj2[i][j];

			if (node_scc_id[here] != node_scc_id[there])
			{
				scc_adj[node_scc_id[here]].push_back(node_scc_id[there]);
				scc_indgree[node_scc_id[there]]++;
			}
		}
	}

	queue<int> q;
	vector<int> scc_id_check(8001, 0);
	for (int i = 1; i <= n; i++)
	{
		int scc_id = node_scc_id[i];

		//이미 확인한 scc_id일때
		if (scc_id_check[scc_id] == 1)
			continue;

		scc_id_check[scc_id] = 1;

		if (scc_indgree[scc_id] == 0)
		{
			q.push(scc_id);
		}
	}

	vector<int> travel; //scc의 위상 정렬의 순서를 저장한다
	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		travel.push_back(here);

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

			if (scc_indgree[there] == 0)
			{
				q.push(there);
			}
		}
	}

	reverse(travel.begin(), travel.end()); //위상 정렬의 역순을 구한다

	//위상 정렬의 역순을 이용해서 위상정렬의 끝 부터 답을 만들어 나간다 (만들어진 cache를 이용)
	//bottom-up DP와 비슷
	for (int i = 0; i < travel.size(); i++)
	{
		int here = travel[i];

		long long this_max_happy = 0;
		long long this_min_happy = numeric_limits<long long>::max();

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

			this_max_happy = max(this_max_happy, cache_max_happy[there]);
			this_min_happy = min(this_min_happy, cache_min_happy[there]);
		}

		this_max_happy = max(this_max_happy, scc_id_max_happy[here]);
		this_min_happy = min(this_min_happy, scc_id_min_happy[here]);

		cache_max_happy[here] = this_max_happy;
		cache_min_happy[here] = this_min_happy;
	}

	for (int i = 1; i <= n; i++)
	{
		cout << cache_max_happy[node_scc_id[i]] - cache_min_happy[node_scc_id[i]] << "\n";
	}

	return 0;
}