백준 4103 ATM

문제링크는 여기

풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)

헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.

위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

enqueue({ start_v, cost[start_v] });
while (q.size()) {
    auto n = q.front(); q.pop();
    max_dist[n.v] = max(max_dist[n.v], n.w);
    for (auto adj : adj_list[n.v]) {
        max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj]=1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}

1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 

따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
if (start_v == -1) for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
else max_dist[start_v] = cost[start_v];
vi cal(max_v + base1); cal[start_v] = 1;
while (q.size()) {
    auto n = q.front(); q.pop();
    for (auto adj : adj_list[n.v]) {
        if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}

코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

/*{{{*/
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#define FileInput freopen("input.txt", "rt", stdin)
#else
#define dbg(...)
#define FileInput
#endif
//#define int long long
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define CASE_T int ___T; cin>>___T;for(int cs=1;cs<=___T;cs++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define IN(n) int n;cin>>n
#define IN2(a,b) int a,b;cin>>a>>b
#define OUT(x) cout << (x) << endl
template <class T>
void OUTV(vector<T>& v) { REP(i, SZ(v)) cout << v[i] << (i + 1 == SZ(v) ? '\n' : ' '); }
typedef long long ll;
const int INF = (int)1e9;
/*}}}*/
 
struct result { vvi scc_list; vvi scc_adj_list; vi scc_cost; int scc_start_v; vi scc_end_v; };
result scc_dag_kosaraju(int max_v, int start_v, vi& end_v, vvi& adj_list, vvi& adj_rlist, vi& cost, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++) if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix); int scc_start_v = -1; vi scc_end_v(scc_ix), scc_cost(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        if (u == start_v) scc_start_v = scc[u];
        if (end_v[u]) scc_end_v[scc[u]] = 1;
        scc_cost[scc[u]] += cost[u];
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc_list, scc_adj_list, scc_cost, scc_start_v, scc_end_v };
}
struct node { int v, w; };
using vvn = vector<vector<node>>;
struct result2 { vi max_dist; int max_value; vi path; };
result2 longest(int max_v, int start_v, vvi& adj_list, vi& in_edge, vi& cost, vi& end_v, int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF);
    vi from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0) return false;
        q.push(n);
        return true;
    };
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    if (start_v == -1) for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
    else max_dist[start_v] = cost[start_v];
    vi cal(max_v + base1); cal[start_v] = 1;
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
            in_edge[adj]--;
            if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
        }
    }
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (end_v[i] && max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    FileInput;
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
    vi cost(V + 1);
    REP1(i, V)cin >> cost[i];
    IN2(S, P);
    vi end_v(V + 1);
    REP(i, P) { IN(p); end_v[p] = 1; }
    auto r = scc_dag_kosaraju(V, S, end_v, adj_list, adj_list2, cost, true);
    int N = SZ(r.scc_adj_list) - 1;
    vi in_edge(N + 1);
    REP1(u, N) for (auto v : r.scc_adj_list[u])in_edge[v]++;
    auto r2 = longest(N, r.scc_start_v, r.scc_adj_list, in_edge, r.scc_cost, r.scc_end_v, true);
    OUT(r2.max_value);
    return 0;
}