글 읽기 - 4013 ATM 질문입니다.

opop20207 4년 전 2

DFS로 SCC를 구하고

SCC에는 그 SCC를 전부 돌았을때 얻을 수 있는 금액을 넣어줬습니다.

그리고 레스토랑의 위치를 bool로 표시해두고

SCC간의 인접리스트를 만들어

visit을 현재 위치에서 얻을수 있는 값으로 갱신해주면서 BFS를 돌렸습니다.

코드가 다소 길지만 조언 주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };
const int ddx[8] = { -1,-1,-1,0,0,1,1,1 };
const int ddy[8] = { -1,0,1,-1,1,-1,0,1 };
const int INF = 0x7fff5037;
const ll INF_LL = 0x7fffffffffffffff;
bool cidx(ll x, ll y, ll N, ll M) { return x >= 0 && x < N && y >= 0 && y < M; }
#define X first
#define Y second
#define pb push_back
#define sz(a) ((int)(a.size()))
#define sf1(a) cin >> a
#define sf2(a,b) cin >> a >> b
#define sf3(a,b,c) cin >> a >> b >> c
#define sf4(a,b,c,d) cin >> a >> b >> c >> d
#define sf5(a,b,c,d,e) cin >> a >> b >> c >> d >> e
#define pf1(a) cout << (a) << ' '
#define pf2(a,b) cout << (a) << ' ' << (b) << ' '
#define pf3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << ' '
#define pf4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' '
#define pf5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' '
#define pfn0() cout << '\n'
#define pfn1(a) cout << (a) << '\n'
#define pfn2(a,b) cout << (a) << ' ' << (b) << '\n'
#define pfn3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << '\n'
#define pfn4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << '\n'
#define pfn5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << '\n'
#define pfv(v) for(auto t : v) pf1(t)
int N, M;
int dfsn[500100], sn[500100], sncnt, dfscnt;
int money[500100];
bool finished[500100];
int visit[500100];
vector<pair<int, bool>> SCC;
vector<int> adj[500100];
vector<int> SCC_adj[500100];
stack<int> s;
queue<pii> q;

int DFS(int cur) {
	dfsn[cur] = dfscnt++;
	s.push(cur);

	int res = dfsn[cur];
	for (auto next : adj[cur]) {
		if (dfsn[next] == 0) res = min(res, DFS(next));
		else if (!finished[next]) res = min(res, dfsn[next]);
	}

	if (res == dfsn[cur]) {
		int sum = 0;
		while (1) {
			int t = s.top();
			s.pop();
			finished[t] = true;
			sn[t] = sncnt;
			sum += money[t];
			if (t == cur) break;
		}
		SCC.pb({ sum,false });
		sncnt++;
	}
	return res;
}

int ret = 0;
void BFS() {
	while (!q.empty()) {
		int cx = q.front().X;
		int cc = q.front().Y;
		q.pop();
		if (SCC[cx].Y == true) ret = max(ret, cc);
		for (auto temp : SCC_adj[cx]) {
			int nx = temp;
			int nc = cc + SCC[nx].X;
			if (visit[nx] < nc) {
				visit[nx] = nc;
				q.push({ nx,nc });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	sf2(N, M);
	for (int i = 0; i < M; i++) {
		int t1, t2;
		sf2(t1, t2);
		t1--, t2--;
		adj[t1].pb(t2);
	}
	for (int i = 0; i < N; i++) {
		sf1(money[i]);
	}
	for (int i = 0; i < N; i++) {
		if (dfsn[i] == 0) DFS(i);
	}
	for (int i = 0; i < N; i++) {
		for (auto temp : adj[i]) {
			if (sn[i] == sn[temp]) continue;
			SCC_adj[sn[i]].push_back(sn[temp]);
		}
	}
	int start, resnum;
	sf2(start, resnum);
	for (int i = 0; i < resnum; i++) {
		int k;
		sf1(k);
		SCC[sn[k]].Y = true;
	}
	q.push({ sn[start],SCC[sn[start]].X });
	visit[start] = SCC[sn[start]].X;
	BFS();
	pfn1(ret);
}

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

문제

문제

출처

ICPC

4013 ATM 질문입니다.

opop20207 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말