여행 계획 세우기

안녕하세요. 오늘은 여행 계획을 세워볼 거예요.

문제

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

아이디어

ATM 문제와 동일합니다.

하지만 불가능한 경우를 고려해야합니다.

그래서 DP의 초깃값을 -2e9로 둔 다음에 문제를 풀고 출력할때 max(정답값, 0)을 출력해주면 됩니다.

소스코드

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

vector <int> v1[10101], v2[10101]; //정방향, 역방향
stack <int> stk;
bool visited[10101] = { 0 };

vector <int> scc;

void dfs1(int node)
{
	visited[node] = true;
	for (int next : v1[node])
		if (!visited[next])
			dfs1(next);
	stk.push(node);
}
void dfs2(int node)
{
	visited[node] = true;
	scc.push_back(node);
	for (int next : v2[node])
		if (!visited[next])
			dfs2(next);
}

int GroupN;
int GroupNum[10101] = { 0 };
int Start, End, GroupSize[10101] = { 0 };
int dp[10101] = { 0 }, indegree[10101] = { 0 };
vector <int> topological[10101]; //위상정렬을 할 때 그룹 간선

void topology_sort() //위상정렬
{
	Start = GroupNum[Start];
	queue <int> q;
	bool able = false; //맨 처음부터 보다가 start를 만나면 flag를 true로 변환 -> 최댓값 계산 시작

	for (int i = 1; i <= GroupN; i++)
	{
		dp[i] = -2e9;
		if (indegree[i] == 0) //들어오는게 없으면
			q.push(i);
	}

	dp[Start] = GroupSize[Start];
	while (q.size())
	{
		int cur = q.front();
		q.pop();
		if (cur == Start) able = true;
		if (able == true && dp[cur] == 0) continue;

		for (int next : topological[cur])
		{
			if (able == true)
				dp[next] = max(dp[next], dp[cur] + GroupSize[next]);

			indegree[next]--;
			if (indegree[next] == 0)
				q.push(next); //0이 되면 넣기
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, i, a, b;
	cin >> N >> M >> Start >> End;
	for (i = 0; i < M; i++)
	{
		cin >> a >> b;
		v1[a].push_back(b);
		v2[b].push_back(a);
	}

	//일단 레스토랑의 종류 빼고 다 입력받음
	//SCC할 차례

	for (i = 1; i <= N; i++) visited[i] = false;
	for (i = 1; i <= N; i++)
		if (visited[i] == false)
			dfs1(i);
	for (i = 1; i <= N; i++) visited[i] = false;

	int idx = 0;
	while (stk.size())
	{
		int node = stk.top();
		stk.pop();
		if (visited[node]) continue;
		dfs2(node);

		idx++;
		GroupSize[idx] = scc.size();
		for (int cur : scc) GroupNum[cur] = idx; //idx 번째 그룹에 속해있음
		scc.clear();
	}
	GroupN = idx; //그룹 수

	//현재상태: S각각의 노드는 몇번 그룹에 속해있는지 정의되어있음
	//이제 위상정렬 및 DP를 할거임

	for (i = 1; i <= N; i++)
	{
		int from = i;
		for (int to : v1[i])
		{
			if (GroupNum[from] != GroupNum[to]) //다른 그룹에 있으면
			{
				topological[GroupNum[from]].push_back(GroupNum[to]);
				indegree[GroupNum[to]]++;
			}
		}
	}

	topology_sort();

	cout << max(dp[GroupNum[End]], 0);
}

감사합니다.