Boj 4013) Atm

문제

백준 4013

설명

일단 누가봐도 Tree 에서의 DP 문제이다. 하지만 Cycle Graph 에서는 DP 을 사용하기가 어렵다. 이미 방문한 Node 와 Cycle 간의 구분이 힘들기 때문이다. 그래서 SCC 를 사용해 DAG 로 만들 필요가 있다.

SCC 를 이용한 그래프 압축을 했다면 DP 를 수행할 수 있다. 이를 구현하는 법은 여러가지겠지만 DFS 를 이용한 아래의 방법은 두가지 포인트를 갖는다.

1. 이제 Graph 의 각 Node 가 아니라 SCC 전체의 값을 사용해 값을 업데이트 해간다. DAG 의 특성 상 SCC 가 달라지는 지점에 한번만 SCC 의 값을 사용해도 충분하다.
2. 계산된 값을 저장하는 단위는 Vertex 단위가 아니라 SCC 단위로 한다. 다시말해 아래 코드의 dp[] 에 사용되는 인덱스가 SCC 의 인덱스어야 한다는 것이다. 그렇지 않으면 같은 SCC 의 Node 라도 값이 다르게 되어 문제가 발생한다. 이 부분이 디버그해서 잡아내기가 힘드므로 주의하자.

여기에 추가로 시작지점과 종료후보지점을 처리해야한다.

• 시작지점은 문제를 간단하게 해준다. 시작지점에서 도달 불가능한 Node 는 탐색할 필요가 없기 때문이다. 일반적 SCC 가 모든 Node 에 대해서 한번씩 탐색을 해야한다면 여기서는 시작지점에서만 DFS 를 돌리면 된다.
• 종료후보지점은 DFS() 를 수행할 때 종료지점에 도달했는지를 기록해서 수행한다. 단순히 dp[] 에 정수를 저장해 음수 등으로 종료지점 도달여부를 수행하면 일이 복잡해진다. bool 값을 따로 쓰자.

시간 복잡도

O(\(\vert \mathrm{V} \vert + \vert \mathrm{E} \vert\))

코드

const int MAX_IN = 500001;

vector<int> lines[MAX_IN];
stack<int> st;
int visits[MAX_IN], n_visit;
int roots[MAX_IN];

bool bRest[MAX_IN];
int cashes[MAX_IN];
vector<pair<int, bool>> scces;

int SCC(int cur)
{
	int res = visits[cur] = ++n_visit;
	st.push(cur);

	for (auto l : lines[cur])
	{
		if (roots[l]) continue;
		if (visits[l]) res = min(res, visits[l]);
		else res = min(res, SCC(l));
	}

	if (res == visits[cur])
	{
		auto& scc = scces.emplace_back();
		const int th = scces.size();
		while (1)
		{
			int tmp = st.top();
			roots[tmp] = th;
			scc.first += cashes[tmp];
			scc.second |= bRest[tmp];
			st.pop();
			if (tmp == cur) break;
		}
	}

	return res;
}

pair<int, bool> dp[MAX_IN];
pair<int, bool> DFS(int cur, int parent = -1)
{
	if (visits[cur] == 0) return dp[roots[cur]];
	visits[cur] = 0;

	auto& res = dp[roots[cur]]; // 초기 {0, false} 상태
	for (auto l : lines[cur])
 	{
		auto t = DFS(l, cur);
		if (t.second)
		{
			res.second |= true;
			res.first = max(res.first, t.first);
		}
	}

	auto& scc = scces[roots[cur] - 1];
	res.second |= scc.second;
	if (res.second && (parent == -1 || roots[cur] != roots[parent])) // Component 전체값 업데이트
		res.first += scc.first;
	
	return res;
}

int main()
{
	int n, m; cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b; cin >> a >> b;
		lines[a].push_back(b);
	}
	for (int i = 1; i <= n; i++) cin >> cashes[i];

	int S, P; cin >> S >> P;
	for (int i = 0; i < P; i++)
	{
		int t; cin >> t;
		bRest[t] = true;
	}

	SCC(S);
	cout << DFS(S).first;
}