boj, 백준) 4013. ATM

#include <bits/stdc++.h>
using namespace std;
#define INF 2000001000
#define MAX_V 500010
vector<vector<int>> vt;
vector<vector<int>> rvt;
vector<vector<int>> scc;
vector<int> my_scc;
bool visited[MAX_V];
vector<int> scc_size;
stack<int> st;
vector<int> cost;
vector<int> dp;
vector<vector<int>> in;
vector<int> out[MAX_V];

vector<int> candi;

void dfs(int x) {
	visited[x] = true;
	for (auto n : vt[x]) {
		if (visited[n]) continue;
		dfs(n);
	}
	st.push(x);
}

int r;

void dfss(int x, int t) {
	visited[x] = true;
	for (auto n : rvt[x]) {
		if (visited[n]) continue;
		dfss(n, t);
	}
	scc[t].push_back(x);
	my_scc[x] = t;
	scc_size[t] += cost[x];
}

//vector<int> scc[MAX_V];


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vt.resize(n + 1);
	rvt.resize(n + 1);
	scc.resize(n + 1);
	my_scc.resize(n + 1);
	scc_size.resize(n + 1);
	cost.resize(n + 1);
	dp.resize(n + 1);
	in.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		vt[x].push_back(y); rvt[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) cin >> cost[i];

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) dfs(i);
	}
	int r = 0;
	memset(visited, 0, sizeof(visited));
	while (!st.empty()) {
		int t = st.top(); st.pop();
		if (visited[t]) continue;
		dfss(t, r++);
	}

	int s, p;
	cin >> s >> p;
	s = my_scc[s];
	

	for (int i = 0; i < p; i++) {
		int t; 
		cin >> t; 
		candi.push_back(my_scc[t]);
	}

	for (int i = 1; i <= n; i++) {
		for (auto nx : vt[i]) {
			if (my_scc[nx] != my_scc[i]) {
				in[my_scc[nx]].push_back(my_scc[i]);
				out[my_scc[i]].push_back(my_scc[nx]);
			}
		}
	}

	vector<int> indegree;
	indegree.resize(r);

	for (int i = 0; i < r; i++) {
		sort(in[i].begin(), in[i].end());
		in[i].erase(unique(in[i].begin(), in[i].end()), in[i].end());
		out[i].erase(unique(out[i].begin(), out[i].end()), out[i].end());
		indegree[i] = in[i].size();
	}

	for (int i = 0; i < r; i++) dp[i] = 0;
	
	queue<int> q;
	q.push(s);
	dp[s] = scc_size[s];

	while (!q.empty()) {
		int t = q.front();
		q.pop();
		for (auto nx : out[t]) {
			//dp[nx] = max(dp[nx], dp[t] + scc_size[nx]);
			if (dp[nx] < dp[t] + scc_size[nx]) {
				dp[nx] = dp[t] + scc_size[nx];
				q.push(nx);
			}
		}
	}
	int M = 0;
	for (auto x : candi) M = max(M, dp[x]);
	cout << M;
}

1. 풀이 

scc로 묶어주고 시작점부터 bfs를 돌려주면 된다. 풀이가 왜 맞는지 아직도 모르겠다... p2는 너무 어렵다...