APIO2009「ATM」解いた

Programming JOI
  • 前回の記事でやった強連結成分分解とトポロジカルソートの結果を利用してDPすればいいだけ。
  • ただし、この過程ででてくるDFSを再帰でそのまま実装するとスタックオーバーフローを起こす。おそらく自前スタックで書けということだろう。
    • 変数をスタックに移すくらいならいいのだが、再帰を自前処理するのはプライドが許さないので、プリプロセッサ使いの技を使って無理矢理再帰を展開してスタックオーバーフローを回避した。
  • 追記:APMOとAPIOをさっきまで間違えていた。死にたい

スタックオーバーフロー対策前版

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <deque>
#include <climits>

using namespace std;

int n,m,s,p;
vector<int> price;
vector<bool> isgoal;
vector<vector<int> > edg;

vector<vector<int> > scc;
vector<int> v_num;
vector<int> v_lnk;
vector<bool> v_instack;
vector<int> v_stack;
int scc_time;
void scc_visit(int v) {
    v_lnk[v] = v_num[v] = scc_time++;
    v_stack.push_back(v);v_instack[v] = true;
    for(int i = 0; i < (int)edg[v].size(); i++) {
        int u = edg[v][i];
        if(!v_num[u]) {
            scc_visit(u);
            v_lnk[v] = min(v_lnk[v], v_lnk[u]);
        } else if(v_instack[u]) {
            v_lnk[v] = min(v_lnk[v], v_num[u]);
        }
    }
    if(v_num[v] == v_lnk[v]) {
        scc.push_back(vector<int>());
        while(true) {
            int u = v_stack.back();v_stack.pop_back();
            v_instack[u] = false;
            scc.back().push_back(u);
            if(v == u) {
                break;
            }
        }
    }
}
void scc_start() {
    scc.clear();
    v_num.clear();v_num.resize(n);
    v_lnk.clear();v_lnk.resize(n);
    v_instack.clear();v_instack.resize(n);
    v_stack.clear();
    scc_time = 1;
    scc_visit(s);
}
int main(int argc, char**argv)
{
    scanf("%d%d", &n, &m);
    edg.resize(n);
    for(int i = 0; i < m; i++) {
        int f,t;
        scanf("%d%d", &f, &t);f--;t--;
        edg[f].push_back(t);
    }
    price.resize(n);
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        price[i] = x;
    }
    scanf("%d%d", &s, &p);s--;
    //isgoal.resize(n);
    isgoal = vector<bool>(n, false);
    for(int i = 0; i < p; i++) {
        int x;
        scanf("%d", &x);x--;
        isgoal[x] = true;
    }
    scc_start();
    int price_max = 0;
    vector<int> scc_to_num(n);
    for(int i = 0; i < (int)scc.size(); i++) {
        for(int j = 0; j < (int)scc[i].size(); j++) {
            scc_to_num[scc[i][j]] = i;
        }
    }
    vector<int> price_maxes(scc.size(), INT_MIN);
    price_maxes[scc_to_num[s]] = 0;
    for(int i = (int)scc.size()-1; i >= 0; i--) {
        bool c_isgoal = false;
        for(int j = 0; j < (int)scc[i].size(); j++) {
            price_maxes[i] += price[scc[i][j]];
            c_isgoal = c_isgoal || isgoal[scc[i][j]];
        }
        for(int j = 0; j < (int)scc[i].size(); j++) {
            for(int k = 0; k < (int)edg[scc[i][j]].size(); k++) {
                int u = edg[scc[i][j]][k];
                price_maxes[scc_to_num[u]] = max(price_maxes[scc_to_num[u]], price_maxes[i]);
            }
        }
        if(c_isgoal) {
            price_max = max(price_max, price_maxes[i]);
        }
        //printf("%d(%d),", price_maxes[i], c_isgoal);
    }
    //printf("\n");
    printf("%d;\n", price_max);
    return 0;
}

スタックオーバーフロー対策後版

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <deque>
#include <climits>

using namespace std;

int n,m,s,p;
vector<int> price;
vector<bool> isgoal;
vector<vector<int> > edg;

vector<vector<int> > scc;
vector<int> v_num;
vector<int> v_lnk;
vector<bool> v_instack;
vector<int> v_stack;
int scc_time;
#define scc_visit_open() \
    v_lnk[v] = v_num[v] = scc_time++; \
    v_stack.push_back(v);v_instack[v] = true; \
    for(i = 0; i < (int)edg[v].size(); i++) { \
        if(!v_num[edg[v][i]]) { \
            svstack_v.push_back(edg[v][i]); \
            svstack_i.push_back(0);

#define scc_visit_close() \
            svstack_i.pop_back(); \
            svstack_v.pop_back(); \
            v_lnk[v] = min(v_lnk[v], v_lnk[edg[v][i]]); \
        } else if(v_instack[edg[v][i]]) { \
            v_lnk[v] = min(v_lnk[v], v_num[edg[v][i]]); \
        } \
    } \
    if(v_num[v] == v_lnk[v]) { \
        scc.push_back(vector<int>()); \
        while(true) { \
            v_instack[v_stack.back()] = false; \
            scc.back().push_back(v_stack.back()); \
            if(v == v_stack.back()) { \
                v_stack.pop_back(); \
                break; \
            } \
            v_stack.pop_back(); \
        } \
    }
vector<int> svstack_v;
vector<int> svstack_i;
void scc_visit() {
#define v svstack_v.back()
#define i svstack_i.back()
#define defrep(x) x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()x()
    defrep(scc_visit_open);
    scc_visit();
    defrep(scc_visit_close);
#undef v
#undef i
}
void scc_start() {
    scc.clear();
    v_num.clear();v_num.resize(n);
    v_lnk.clear();v_lnk.resize(n);
    v_instack.clear();v_instack.resize(n);
    v_stack.clear();
    scc_time = 1;
    svstack_v.reserve(n);
    svstack_i.reserve(n);
    svstack_v.push_back(s);
    svstack_i.push_back(0);
    scc_visit();
}
void proc()
{
    int price_max = 0;
    vector<int> scc_to_num(n);
    for(int i = 0; i < (int)scc.size(); i++) {
        for(int j = 0; j < (int)scc[i].size(); j++) {
            scc_to_num[scc[i][j]] = i;
        }
    }
    vector<int> price_maxes(scc.size(), INT_MIN);
    price_maxes[scc_to_num[s]] = 0;
    for(int i = (int)scc.size()-1; i >= 0; i--) {
        bool c_isgoal = false;
        for(int j = 0; j < (int)scc[i].size(); j++) {
            price_maxes[i] += price[scc[i][j]];
            c_isgoal = c_isgoal || isgoal[scc[i][j]];
        }
        for(int j = 0; j < (int)scc[i].size(); j++) {
            for(int k = 0; k < (int)edg[scc[i][j]].size(); k++) {
                int u = edg[scc[i][j]][k];
                price_maxes[scc_to_num[u]] = max(price_maxes[scc_to_num[u]], price_maxes[i]);
            }
        }
        if(c_isgoal) {
            price_max = max(price_max, price_maxes[i]);
        }
    }
    //printf("\n");
    printf("%d;\n", price_max);
}
int main(int argc, char**argv)
{
    scanf("%d%d", &n, &m);
    edg.resize(n);
    for(int i = 0; i < m; i++) {
        int f,t;
        scanf("%d%d", &f, &t);f--;t--;
        edg[f].push_back(t);
    }
    price.resize(n);
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        price[i] = x;
    }
    scanf("%d%d", &s, &p);s--;
    isgoal.resize(n);
    for(int i = 0; i < p; i++) {
        int x;
        scanf("%d", &x);x--;
        isgoal[x] = true;
    }
    scc_start();
    proc();
    return 0;
}