BOJ 4013 - ATM

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

4013번: ATM

 

중요한 문제라고 생각함. 유니온파인드 말고 SN, sn[MAX] 쓰면 더 쉽다.

 

scc를 나누는데 레스토랑이 있는지, 시작점인지 등등 정보를 저장해 둔다.

그리고 scc에 대해 위상정렬을 돌린다. 이때, ind가 0인 지점에서 위상정렬이 돌아갈텐데, 그 부분이 시점이 아닐 수도 있다.

따라서 시작점에서 도달 가능한 scc정점을 의미하는 boolean형 sCal[MAX]를 만들고, 시작점만 true로 한다.

그렇게 되면 위상정렬을 돌릴 떄 sCal==true인 곳에서만 인출가능 금액을 갱신해 준다.

 

마지막에 레스토랑을 들어갈 때 얻을 수 있는 최대 금액은 레스토랑이 있는 scc정점이고 sCal==true인 곳에 대해서만 비교해가면서 찾으면 된다.

 

 

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#define MAX 500001
using namespace std;
typedef long long ll;

//for scc//
int id, dfsn[MAX];
bool finished[MAX];
vector<int> adj[MAX];
stack<int> s;
int scc[MAX], sccSize;

int cash[MAX];
bool hasRes[MAX], sHasRes[MAX];

int find(int a) {
	if (scc[a] == a) return a;
	return scc[a] = find(scc[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	scc[a] = b;
}

int makeSCC(int curr) {
	dfsn[curr] = ++id;
	s.push(curr);

	int parent = dfsn[curr];
	for (int next : adj[curr]) {
		if (dfsn[next] == 0) parent = min(parent, makeSCC(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}
	if (parent == dfsn[curr]) {
		int uf = s.top();
		while (1) {
			int t = s.top();
			s.pop();
			finished[t] = true;
			merge(t, uf);
			if (t == curr) break;
		}
		sccSize++;
	}

	return parent;
}

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

	int n, m, s, p; cin >> n >> m;
	for (int i = 1; i <= n; i++) scc[i] = i;

	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
	}
	for (int i = 1, input; i <= n; i++) {
		cin >> input;
		cash[i] = input;
	}
	cin >> s >> p;
	for (int i = 0, input; i < p; i++) {
		cin >> input;
		hasRes[input] = true;
	}

	for (int i = 1; i <= n; i++)
		if (dfsn[i] == 0) makeSCC(i);
	//scc추출완료

	vector<int> sAdj[MAX];
	int sStart;
	int sCash[MAX] = { 0 }, sInd[MAX] = { 0 };
	for (int i = 1; i <= n; i++) {
		int sIdx = find(i);
		sCash[sIdx] += cash[i];
		if (hasRes[i]) sHasRes[sIdx] = true;
		if (i == s) sStart = sIdx;
		for (int j : adj[i]) {
			int sJdx = find(j);
			if (sIdx == sJdx) continue;
			sAdj[sIdx].push_back(sJdx);
			sInd[sJdx]++;
		}
	}
	//scc정제완료

	queue<int> q;
	int sMax[MAX]; // 각 scc의 결과값
	bool flag[MAX] = { 0 }, sCal[MAX] = { 0 };
	for (int i = 1; i <= n; i++) {
		int idx = find(i);
		sMax[idx] = sCash[idx];
		if (idx == sStart) sCal[idx] = true;
		if (flag[idx]) continue;
		if (sInd[idx] == 0) {
			q.push(idx);
			flag[idx] = true;
		}
	}

	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int next : sAdj[curr]) {
			if (sCal[curr]) {
				sMax[next] = max(sMax[next], sMax[curr] + sCash[next]);
				sCal[next] = true;
			}
			if (--sInd[next] == 0) q.push(next);
		}
	}

	int rst = 0; 
	//fill(flag, flag + MAX, false);
	for (int i = 1; i <= n; i++) {
		int idx = find(i);
		if (sHasRes[idx] && sCal[idx]) rst = max(rst, sMax[i]);
	}
	cout << rst << '\n';
		
	
}