글 읽기 - 코라사주 알고리즘을 이용한 풀이

tjtjdals 3년 전 0

코라사주를 이용해 풀이를 시도해봤으나 틀렸습니다가 나왔습니다. 원인을 못 찾아 조언 혹은 반례를 부탁드립니다.

1. 그래프를 순회하며 stack을 구성할 때 방문하지 못하는 노드는 방문불가능한 노드라 생각하여 배제 시켰습니다.

2. 스택은 위상정렬된 상태이므로 항상 탐색하는 노드의 부모노드들은 사이클 검사를 마쳤을 것이라 생각하여 그중에서 가장 큰 현금을

상속한다음 탐색하는 노드와 사이클을 이루는 모든 노드들의 현금을 더해, 탐색 노드 + 사이클을 이루는 노드 들의 cash 를 갱신하였습니다.

3. 2번의 탐색 노드 + 사이클을 이루는 노드 를 갱신하며 restaurant 이 위치한 노드라면 answer 를 갱신하였습니다.

잘못 생각했던 걸까요?... 조언 부탁드립니다.

#include <cstdio>
#include <vector>
#include <stack>

using namespace std;


int					N, M;
int					cash[500001];
bool				restaurant_mask[500001];
bool				scc_mask[500001];
bool				visited[500001];
vector<int>			graph[500001];
vector<int>			re_graph[500001];
stack<int>			stk;
stack<int>			scc_stk;
int					answer;


void				construct_stk(int node)	//코사라주 
{										    //visited[node] == false 으로 남으면
	vector<int>::iterator	v_iter;			//시작정점에서 방문 불가능한 노드

	visited[node] = true;
	for (v_iter = graph[node].begin(); \
			v_iter != graph[node].end(); v_iter++)
	{
		if (!visited[*v_iter])
			construct_stk(*v_iter);
	}
	stk.push(node);
}

int					scc(int node)
{
	int						cash_sum;
	vector<int>::iterator	v_iter;

	scc_mask[node] = true;
	scc_stk.push(node);
	cash_sum = cash[node];
	for (v_iter = re_graph[node].begin(); \
			v_iter != re_graph[node].end(); v_iter++)
	{
		if (!scc_mask[*v_iter] && visited[*v_iter])	//방문 가능한 노드만으로 scc 구성
			cash_sum += scc(*v_iter);
	}
	return (cash_sum);
}

int					main(void)
{
	int				S, P;
	int				start_node, target_node, heritage_cash;
	int				restaurant_total, restaurant_idx;
	vector<int>::iterator	v_iter;

	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &S, &P);
		graph[S].push_back(P);
		re_graph[P].push_back(S);
	}
	for (int i = 1; i <= N; i++)
		scanf("%d", cash + i);
	scanf("%d %d", &start_node, &restaurant_total);
	for (int i = 0; i < restaurant_total; i++)
	{
		scanf("%d", &restaurant_idx);
		restaurant_mask[restaurant_idx] = true;
	}
	construct_stk(start_node);
	while (!stk.empty())
	{
		heritage_cash = 0;
		target_node = stk.top();
		stk.pop();
		for (v_iter = re_graph[target_node].begin(); \			//target_node 로의 in-bound 노드 검사
				v_iter != re_graph[target_node].end(); v_iter++)//stk은 위상정렬된 상태이므로 부모노드
			if (scc_mask[*v_iter] && cash[*v_iter] > heritage_cash)//는 scc구성을 마침 따라서 in-bound 중
				heritage_cash = cash[*v_iter];			        //최대 현금을 상속 받음
		heritage_cash += scc(target_node);			        	//
		while (!scc_stk.empty())				               	//target_node와 사이클을 이루는 노드들을
		{								                        //상속 현금 + 사이클 내 현금으로 갱신
			cash[scc_stk.top()] = heritage_cash;
			if (restaurant_mask[scc_stk.top()] && heritage_cash > answer)
				answer = heritage_cash;			            	//restaurant가 위치한 노드일 경우
			scc_stk.pop();					                	//answer 갱신
		}
		while (!stk.empty() && scc_mask[stk.top()])
			stk.pop();
	}
	printf("%d\n", answer);
	return (0);
}

tjtjdals 3년 전 0

로직에는 문제가 없었으나,

in-bound 노드를 검사할 때 target_node 만이 아닌 해당 사이클로 들어오는 모든 간선을 체크해주는 걸로 바꾸니 이상 없었습니다.

비슷한 문제를 가지신 분 있으시면 참고하시면 좋을 것 같습니다.

tjtjdals 3년 전 0

http://apio-olympiad.org/2009/

사용했던 테스트 파일 남겨드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코라사주 알고리즘을 이용한 풀이 - 틀렸습니다.(c++)

tjtjdals 3년 전 0

tjtjdals 3년 전 0

tjtjdals 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말