http://www.lydsy.com/JudgeOnline/problem.php?id=1179

强联通缩点，DAG DP

const int N = int(5e5) + 9;
VI _adj[N], adj[N]; int _bonus[N], bonus[N];
bool _isBar[N], isBar[N];
int _n, n;
int _st;


int dfn[N], low[N], bel[N], sta[N], Time, top; VI con[N];

#define v (*it)
void tarjan(int u){
    
    low[u] = dfn[u] = ++Time;
    sta[top++] = u;
    
    ECH(it, _adj[u]){
        if (dfn[v] < dfn[u]){
            if (!dfn[v]) tarjan(v);
            checkMin(low[u], low[v]);
        }
    }
    
    if (low[u] == dfn[u]){
        int t;
        do{
            t = sta[--top];
            con[n].PB(t);
            bel[t] = n;
            dfn[t] = INF;
            bonus[n] += _bonus[t];
            isBar[n] |= _isBar[t];
        } while(t != u);
        ++n;
    }
}


void scc(){
    
    REP_1(u, _n) if(!dfn[u]) tarjan(u);
    
    REP_1(u, _n) ECH(it, _adj[u]){
        int a = bel[u], b = bel[v];
        if (a == b) continue;
        adj[b].PB(a);
    }
}

int F[N]; int f(int u){
    int &res = F[u];
    if (res == -1){
        int t = -INF;
        ECH(it, adj[u]) checkMax(t, f(v));
        res = t >= 0 ? t + bonus[u] : -INF;
    }
    return res;
}

int main(){
    
#ifndef ONLINE_JUDGE
    freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
    //freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
    
    RD(_n); Rush{
        int a, b; RD(a, b); --a, --b;
        _adj[a].PB(b);
    }
    REP(i, _n) RD(_bonus[i]);
    --RD(_st); Rush _isBar[RD()-1] = true;
    
    scc();
    
    FLC(F, -1); int st = bel[_st]; F[st] = bonus[st];
    int z = 0; REP(i, n) if (isBar[i]) checkMax(z, f(i));
    
    /*REP(i, n){
        ECH(it, con[i]) cout << v << " ";
        cout << bonus[i] << endl;
    }*/
    
    cout << z << endl;
}

Posted by xiaodao
Category: BZOJ